[Algorithm][动态规划][路径问题][不同路径][不同路径Ⅱ][珠宝的最高价值]详细讲解

---

1.不同路径

1.题目链接

• 不同路径

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 走到dp[i][j]的时候，一共有多少种方式
      

  • 推导状态转移方程

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

  • 初始化：dp表多开一行和一列虚拟结点，避免处理边界

    • dp[0][1] = 1 || dp[1][0] = 1
      

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

• 上述如果dp表不多开那一行和一列虚拟结点会怎么样？
  • 需要做边界处理，将第一列和第一行先初始化为1

---

3.代码实现

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

---

2.不同路径 II

1.题目链接

• 不同路径 II

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 走到dp[i][j]的时候，一共有多少种方式
      

  • 推导状态转移方程

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

  • 初始化：dp表多开一行和一列虚拟结点，避免处理边界

    • dp[0][1] = 1 || dp[1][0] = 1
      

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

---

3.代码实现

int uniquePathsWithObstacles(vector<vector<int>>& ob) 
{int n = ob.size(), m = ob[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));dp[0][1] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(ob[i - 1][j - 1] == 0) // 注意下表映射关系{dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[n][m];
}

---

3.珠宝的最高价值

1.题目链接

• 珠宝的最高价值

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 到达dp[i][j]的时候，此时的最大价值

  • 推导状态转移方程

    • dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + g[i][j]
      

  • 初始化：dp表多开一行和一列虚拟结点，避免处理边界

    • 第一行和第一列全部初始化为0即可

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：dp[n][m]

---

3.代码实现

int jewelleryValue(vector<vector<int>>& frame) 
{int n = frame.size(), m = frame[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];}}return dp[n][m];
}