动态规划

核心思想：小大化小

大规模问题的依赖于小规模问题

类似思想算法的还有：递归，分治法

动态规划 DP

贪心法 Greedy

实现方式

1. 记忆化搜索

   （自顶向下的动态规划）

2. 多重循环

   （自底向上的动态规划）

状态：坐标

方程：到哪去

初始化：终点

答案：起点

什么东西需要初始化：可以直接放在公式里面求出来的部分

可以套公式：不会出现越界或者是算不出来的情况的

自底向上、自顶向下

自底向上：正着依赖，倒着循环

自顶向下：正着循环，倒着依赖

三大类问题

1. 最值
2. 可行性
3. 方案总数

动归四要素

动规的状态State — 递归的定义

• 用 f[i]或者f[i] 代表在某些特定条件下某个规模更小的问题的答案
• 规模更小用参数 i 之类的来划定
• 状态

  • 基础

    • 坐标
    • 前缀
    • 区间
    • 状压

  • 约束

    • 背包
    • 划分
    • 状态

动规的方程Function --- 递归的拆解

• 上一步从哪来
• 大问题如何拆解为小问题
• f[i]t] = 通过规模更小的一些状态求 max / min / sum / or 来进行推导

动规的初始化Initialize - 递归的出口

• 设定无法再拆解的极限小的状态下的值
• 如f[i][0]或者 f[0][i]

动规的答案Answer — 递归的调用

• 最后要求的答案是什么
• 如f[n][m]或者 max(f[n][0], f[n][1] …f[n][m])

这也就是为什么动态规划可以使用

“递归”版本的记忆化搜索来解决的原因！

算法难的就是递归和动规

不同的路径 Unique Path

dp[i][j] = dp[i-1][j] + dp[i][j-1]

void uniquePath(int m, int n) {
    // state: dp[i][j] 代表0, 0走到i, j的方案数
    int[][] dp = new int[m][n];
    
    // init
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    
    return dp[m - 1][n - 1];
}