动态规划初学

62. 不同路径 - 力扣（LeetCode）

class Solution {public: int uniquePaths(int m, int n) { // vector<vector> dp(m,vector(n,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]; vector dp(n,1); for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ dp[j] += dp[j-1]; } } return dp[n-1]; }};

0. 题目本质（二维真相）

到格子 (i,j) 的所有路线，最后一步只有两种：

• 从上面 (i-1,j) 下来；

• 从左边 (i,j-1) 过来。

所以二维递推一定是：

ways[i][j]=ways[i−1][j]+ways[i][j−1].\\text{ways}[i][j] = \\text{ways}[i-1][j] + \\text{ways}[i][j-1].

1. 一维滚动在干嘛（一句话）

我们不再开整张二维表，而是只拿一行数组 dp 来承载“当前正在处理的这一行”的结果。
关键点：在更新第 i 行第 j 列的这一刻——

• dp[j] 里还没更新，装的是上一行同一列的值 ⇒ 就是“上方”的条数 ways[i-1][j]；

• dp[j-1] 刚更新完，装的是当前行左边格子的值 ⇒ 就是“左方”的条数 ways[i][j-1]。

于是我们写：

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

此时等式左边的两部分，恰好就是上 + 左。这就是为什么它成立。

记住一句：“旧的 dp[j] = 上方；更新后的 dp[j-1] = 左方。”

2. 小例子，按时间顺序看数值怎么流动（m=3, n=4）

目标网格 3×4（行×列），坐标从 (0,0) 到 (2,3)。
初始化第一行只能往右走，所以 dp = [1, 1, 1, 1]，相当于 ways[0][j] = 1。

处理第 i=1 行（也就是第二行）

我们从左到右更新 j=1..3：

• 更新 j=1 前：

  • dp[1]=1（上方 ways[0][1]）

  • dp[0]=1（左方 ways[1][0]，第一列始终为 1）

  • 更新：dp[1] = 1 + 1 = 2 → dp = [1, 2, 1, 1]

• 更新 j=2 前：

  • dp[2]=1（上方 ways[0][2]）

  • dp[1]=2（左方 ways[1][1]，因为刚更新过）

  • 更新：dp[2] = 1 + 2 = 3 → dp = [1, 2, 3, 1]

• 更新 j=3 前：

  • dp[3]=1（上方 ways[0][3]）

  • dp[2]=3（左方 ways[1][2]）

  • 更新：dp[3] = 1 + 3 = 4 → dp = [1, 2, 3, 4]

处理第 i=2 行（第三行）

• j=1：上 dp[1]=2，左 dp[0]=1 → 新 dp[1]=3 → [1,3,3,4]

• j=2：上 dp[2]=3，左 dp[1]=3 → 新 dp[2]=6 → [1,3,6,4]

• j=3：上 dp[3]=4，左 dp[2]=6 → 新 dp[3]=10→ [1,3,6,10]

最后答案 dp[3]=10，与二维解一致（也等于组合数 C(5,2)=10）。

你看到了吗？ 在每个“更新 j 的瞬间”，dp[j] 是上方，dp[j-1] 是左方，所以“上 + 左”自然就对上二维的递推了。

3. 为什么必须“从左到右”？

因为你需要 dp[j-1] 先变成“当前行左边”的值（ways[i][j-1]），这样它才是“左”。
如果你从右往左更新，dp[j-1] 还没更新，仍是“上一行左上”的数，就会变成“上 + 上”，错了。

4. 初始化为全 1 的原因

• 第一行只能一直向右走 → 每格 1 条路 → dp[j]=1；

• 第一列在任何一行也只能一直向下走 → dp[0] 在整个过程始终是 1；
  这也解释了为什么内层循环从 j=1 开始。

5. 一点点“形式化”的说法（口语版归纳）

• 开始处理第 i 行之前：dp[j] 存着上一行 ways[i-1][j]；

• 本行从左到右更新：到 j 时，dp[j-1] 已是 ways[i][j-1]，dp[j] 还是 ways[i-1][j]；相加得到 ways[i][j]，把它写回 dp[j]；

• 这一行全部走完，dp 就变成 ways[i][*]；下一行周而复始。

这就说明每一刻“上 + 左”的含义都不被破坏，所以一维更新等价于二维更新。

6. 放回到代码里再看一眼

int uniquePaths(int m, int n) { vector dp(n, 1); // 第一行 for (int i = 1; i < m; ++i) { // 一行一行推 for (int j = 1; j < n; ++j) { // 从左到右推 dp[j] += dp[j - 1]; // 上(旧dp[j]) + 左(新dp[j-1]) } } return (int)dp[n - 1]; // 右下角}

• dp[j] += dp[j-1]：这句就是把上方和左方相加；

• j 从 1 开始：不破坏第一列“只能向下”的边界；

• 用 long long 是为了中间不溢出（最后再转回 int）。

63. 不同路径 II - 力扣（LeetCode）

class Solution {public: int uniquePathsWithObstacles(vector<vector>& g) { int m = g.size(), n = g[0].size(); vector<vector> dp(m, vector(n,0)); if(g[0][0] == 1 || g[m-1][n-1] == 1) return 0; for(int i = 0; i < m && g[i][0] != 1; i++) dp[i][0] = 1; for(int i = 0; i < n && g[0][i] != 1; i++) dp[0][i] = 1; for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ if(g[i][j] == 0){  dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[m-1][n-1]; }};

343. 整数拆分 - 力扣（LeetCode）

class Solution {public: int integerBreak(int n) { vector dp(n+1, 0); dp[2] = 1; for(int i = 3; i <= n; i++){ int best = 0; { for(int j = 1; j < i ; j++){  int L = max(j, dp[j]);  int R = max(i-j, dp[i-j]);  best = max(best, L*R); } dp[i] = best; } } return dp[n]; }};

96. 不同的二叉搜索树 - 力扣（LeetCode）

class Solution {public: int numTrees(int n) { vector dp(n +1,0); dp[0] = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ dp[i] += dp[j -1] * dp[i-j]; } } return dp[n]; }};