动态规划之路径问题

不同路径

题目：不同路径

思路

• 状态表示：dp[i][j]表示走到[i, j]位置时，一共有多少种方式
• 状态转移方程：到达[i, j]位置有两种方式
  • 从[i - 1, j]到[i, j]；
  • 从[i, j - 1]到[i, j]；
  • 所以，状态转移方程为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
• 初始化：在 dp数组前添加一行和一列，初始化dp[0][1] = 1
• 填表顺序：从上往下，从左往右
• 返回值： 返回 dp[m][n]，从起始位置到达终点位置的路径数
  C++代码

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

不同路径 II

题目：不同路径 II

思路

• 状态表示：dp[i][j]表示走到[i, j]位置时，一共有多少种方式
• 状态转移方程：到达[i, j]位置有两种方式
  • 从[i - 1, j]到[i, j]；
  • 从[i, j - 1]到[i, j]；
  • 如果某个位置[i - 1, j] 或者 [i, j - 1] 上存在障碍物， dp[i][j] = 0
  • 所以，状态转移方程为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
• 初始化：在 dp数组前添加一行和一列，初始化dp[0][1] = 1
• 填表顺序：从上往下，从左往右
• 返回值： 返回 dp[n][m]，从起始位置到达终点位置的路径数
  C++代码

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

珠宝的最高价值

题目：珠宝的最高价值

思路

• 状态表示：dp[i][j]表示走到[i, j]位置时，此时的最大价值
• 状态转移方程：到达[i, j]位置有两种方式
  • 从[i - 1, j]到[i, j]；
  • 从[i, j - 1]到[i, j]；
  • 需要选择其中最大价值的路径
  • 所以，状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1]
• 初始化：在 dp数组前添加一行和一列，将所有值初始化为零
• 填表顺序：从上往下，从左往右
• 返回值： 返回 dp[n][m]，表示最大值

C++代码

class Solution 
{
public:int jewelleryValue(vector<vector<int>>& frame) {int n = frame.size(), m = frame[0].size();vector<vector<int>>dp(n + 1, vector<int>(m + 1));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];}
};

下降路径最小和

题目：下降路径最小和

思路

• 状态表示：dp[i][j]表示走到[i, j]位置时，此时的最小的下降路径

• 状态转移方程：到达[i, j]位置有三种方式

  • 从正上方[i - 1, j]到[i, j]；
  • 从右上方[i + 1, j + 1]到[i, j]；
  • 从左上方[i - 1, j - 1]到[i, j]；
  • 需要选择最小的下降路径
  • 所以，状态转移方程为：dp[i][j] = matrix[i - 1][j - 1] + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))]

• 初始化：添加了一行和两列，

  • 两列：将其值初始化为正无穷大
  • 一行：将其值初始化为 0，以保证后续填表时是正确的

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

• 返回值： 返回dp表中最后一行的最小值dp[n][i]

C++代码

class Solution 
{
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX)); // 两列：将其值初始化为正无穷大for(int i = 0; i < n + 2; i++) dp[0][i] = 0; // 一行：将其值初始化为 0for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dp[i][j] = matrix[i - 1][j - 1] + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]));int ret = INT_MAX;for(int i = 1;i <= n; i++)ret = min(ret, dp[n][i]);return ret;}
};

最小路径和

题目：最小路径和

思路

• 状态表示：dp[i][j]表示走到[i, j]位置时，此时的最小的下降路径和

• 状态转移方程：到达[i, j]位置有两种方式

  • 从左方[i, j - 1]到[i, j]；
  • 从上方[i - 1, j]到[i, j]；
  • 需要选择最小的下降路径
  • 所以，状态转移方程为：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]

• 初始化：

  • 初始化所有位置为正无穷大
  • 特殊位置设置为0，即dp[0][1] = dp[1][0] = 0;

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

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

C++代码

class Solution 
{
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[0][1] = dp[1][0] = 0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];return dp[m][n];}
};

地下城游戏

题目：地下城游戏

思路

• 状态表示：dp[i][j]表示，从[i, j]到达终点，所需的最低健康点数

• 状态转移方程：到达[i, j]位置有两种方式

  • 从下方[i + 1, j ]到[i, j]；
  • 从右方[i , j + 1]到[i, j]；
  • 所以，状态转移方程为：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
  • 由于dungeon[i][j] 可能是一个较大的正数，计算得到的dp[i][j]的值可能会小于等于 0，所以我们将 dp[i][j] 与 1 取最大值，即dp[i][j]=max(1,dp[i][j])；
  • 综上，dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])

• 初始化：我们在 dp 表的最后一行和最后一列分别添加一行和一列

  • 初始化所有位置为正无穷大
  • dp[m][n - 1] = dp[m - 1][n] = 1

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

• 返回值： 返回dp[0][0]

C++代码

class Solution 
{
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int n = dungeon.size(), m = dungeon[0].size();vector<vector<int>>dp(n + 1, vector<int>(m + 1, INT_MAX));dp[n - 1][m] = dp[n][m - 1] = 1;for(int i = n - 1; i >= 0; i --)for(int j = m - 1; j >= 0; j --)dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);return dp[0][0];}
};