【动态规划】零基础解决路径问题（C++）

目录

62.路径问题

解法（动态规划）：

1. 状态表⽰：

2. 状态转移⽅程：

3. 初始化：

4. 填表顺序：

5. 返回值：

不同路径2.0

解法（动态规划）：

1. 状态表⽰：

2. 状态转移：

3. 初始化：

4. 填表顺序：

5. 返回值：

代码

剑指Offer47.礼物的最⼤价值

方程;

代码：

931.下降路径最小和

 代码：

64.最小路径和 

【困难题】 174.地下城游戏（视频讲解）

总结：

---

62.路径问题

解法（动态规划）：

算法思路：

1. 状态表⽰：

对于这种「路径类」的问题，我们的状态表⽰⼀般有两种形式：

• i. [i, j] 位置出发，巴拉巴拉；
• ii. 从起始位置出发，到达[i, j] 位置，巴拉巴拉。

  这⾥选择第⼆种定义状态表⽰的⽅式： dp[i][j] 表⽰：⾛到[i, j] 位置处，⼀共有多少种⽅式。

  2. 状态转移⽅程：

  简单分析⼀下。如果dp[i][j] 表⽰到达[i, j] 位置的⽅法数，那么到达[i, j] 位置之 前的⼀⼩步，有两种情况：

  • i. 从[i, j] 位置的上⽅（ [i - 1, j] 的位置）向下⾛⼀步，转移到[i, j] 位置；
  • ii. 从[i, j] 位置的左⽅（ [i, j - 1] 的位置）向右⾛⼀步，转移到[i, j] 位置。

    由于我们要求的是有多少种⽅法，因此状态转移⽅程就呼之欲出了： dp[i][j] = dp[i - 1] [j] + dp[i][j - 1] 。

    3. 初始化：

    可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：

    • i. 辅助结点⾥⾯的值要「保证后续填表是正确的」；
    • ii. 「下标的映射关系」。

      在本题中，「添加⼀⾏」，并且「添加⼀列」后，只需将dp[0][1] 的位置初始化为1 即可。

      4. 填表顺序：

      根据「状态转移⽅程」的推导来看，

      填表的顺序就是「从上往下」填每⼀⾏，在填写每⼀⾏的时候 「从左往右」。

      5. 返回值：

      根据「状态表⽰」，我们要返回dp[m][n] 的值。

      代码：

      class Solution
      {
      public:
      	int uniquePaths(int m, int n)
      	{
      		vector dp(m + 1, vector(n + 1, 0)); // 创建⼀个 dp表 
      		dp[0][1] = 1; // 初始化 
      		// 填表 
      		for (int i = 1; i