👉 动态规划其实就是动态递推👈

# 要点

递归 + 记忆化 -> 递推 (自下而上的递推)
状态的定义，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).

然后我们就可以发现：

1	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)$

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

# 最后

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

算法动态规划数据结构与算法