:point_right: [动态规划其实就是动态递推]{.label .success}:point_left:

要点

递归+记忆化 -> 递推(自下而上的递推)
状态的定义,opt[n],dp[n],fib[n]
状态转移方程(dp方程)， opt[n]=best_of(opt[n-1],opt[n-2])
最优子结构

例子

斐波那契数列

我们先使用递归的方式，我们实现斐波那契数列.

#include <stdio.h>

int fib1();

int fib2();

int main() {
    printf("fib1(6)=%d\n", fib1(6));
    printf("fib2(6)=%d\n", fib2(6));
    return 0;
}

/**
 * 斐波那契数列实现方案一
 * @param n 第n个数
 * @return n个数的值
 */
int fib1(int n) {

    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else {
        return fib1(n - 1) + fib1(n - 2);
    }
}

/**
 * 斐波那契数列实现方案二
 * @param n 第n个数
 * @return n个数的值
 */
int fib2(int n) {

    if (n <= 1) {
        return 1;
    } else {
        return fib1(n - 1) + fib1(n - 2);
    }
    /// return n<=1?1:fib1(n - 1) + fib1(n - 2);
}

如下图:

算法01-动态规划01-fib.png 此时的时间复杂度为O(2^n).如上图，最后的结果是每个节点是累加起来，那么有多少个节点呢? 2^n个节点。根据这张图,我们可以发现，个别”节点”出现了重复的情况,这个时候我们就用到了记忆化的方式进行优化。

int fib3(int n);

int main() {
    printf("fib3(6)=%d\n", fib3(6));
    return 0;
}

/**
 * 斐波那契数列实现方案三
 * @param n  第n个数
 * @return n个数的值
 */
int mem[100];

int fib3(int n) {
    if (n <= 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    } else if (!mem[n]) {
        mem[n] = fib1(n - 1) + fib1(n - 2);
    }
    return mem[n];
}

这样我们就省去了个别节点的计算过程了.如下图算法01-动态规划01-fib02.png 其中虚线边框的就不用再计算了。

这样的话，我们把时间复杂度优化到了O(n).

然后我们就可以发现：

fib(n) = fib(n-1) + fib(n-2);

这个就是我们的状态转移方程(dp方程)。比较的简单的fib，一般我们就成为这个为递推公式。

计算路线

例题描述

算法01-动态规划02-计算路径.png

只能横着走或者竖着走，假设有一个人总start处,走到end处,一共有多少条路线?

分析

算法02-动态规划03-计算路径02.png

从start到end的所有路线,等于B到end路线加上A到end的路线。因为start要到end，要么到A,从A走到end,要么到B，从B走到end。那么同理B到end就等于C到end的路线到E到end的路线。D到end等于C到end的路线加上D到end的路线. 这是我们可以得出如下的推导公式：

path(start,end)=path(A,end) + path(B,end)

同理:

path(A,end)=path(D,end) + path(C,end) \\ path(B,end) = path(E,end) + path(C,end)

一直到最下面的一行,最下面的这一行的每个点到end的路线只有一条,所以每个都是1,同样的最右侧的一列,每个都是1.如下图. 算法01-动态规划02-计算路径03.png 经过上面的分析,F到end有几条路线呢？两条。由于G右侧是黑色的不能通过，所以G只有1条,H就有2条,就有3条,K有3条,L有1条。所以有了下面的这张图,图中的数字就是路线数. 算法01-动态规划02-计算路径04.png

根据以上的推论我们尝试写出这样的代码:

int countPaths(int[][] grid,int row,int col){
    if(!validSquare(grid,row,col)){
        return 0;
    }
    if(isEnd(grid,row,col)){
        return 1;
    }
    return countPaths(grid,row+1,col) + countPaths(grid,row,col+1);
}

我根据推论可以得出状态转移方程:

if a[i,j] == '白色':
   opt[i,j] = opt[i+1,j] + opt[i,j+1]
else:
   opt[i,j] = 0

程序实现

int uniquePaths(int m, int n){
    int paths[m+1][n+1];
    for(int i=m;i>0;i--){
        paths[i][n] = 1;
    }
    for(int j =n; j>0;j--){
        paths[m][j] = 1;
    }
    for (int i = m-1; i > 0; i--)
    {
        for (int j = n - 1; j > 0 ; j--)
        {
            paths[i][j] = paths[i+1][j] + paths[i][j+1];
        }
    }
    return paths[1][1];
}

DP vs 回溯 vs 贪心

回溯(递归) - 重复计算
贪心 - 永远局部最优
DP - 记录局部最优子结构/多种记录值。(集两者之大成)

三者并没有明显的界限.贪心不是局部最优的时候，回溯避免了重复计算之后，就是了动态规划了。

例题

爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数

解析

如下面的图:

算法01-动态规划03-爬楼梯01.png

因为我们只有两种走法,要么跨一个台阶,要么跨两个台阶。那么如图中我们爬到第10层台阶的走法就等于第9(10-1)层台阶的走法和第8(10-2)层台阶的走法的和。即 $stairs(10)=stairs(9)+stairs(8)$ ,那么我们爬第一层台阶是1种走法,第二层台阶就是2种走法。所以我们就可以得出我们的递推公式：

stairs(n) = stairs(n-1) + stairs(n-2)

我们可以得出，这就是斐波那契数列。

最后

期望与你一起遇见更好的自己