动态规划（路径问题）
1. 不同路径 |
- 状态表示
dp[i][j]表示以i，j为结尾的时候，有多少中路径 - 状态转移方程
- 初始化
初始化的地方采用虚拟节点的办法。辅助节点里面的值要保证后续的填表是正确的，并且下标的映射关系要正确
这里必须保证阴影部分有一个地方为1，这样就能保证初始化是正确的
- 填表
从上到下，从左到右 - 返回值
AC代码：
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); 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]; } };
2. 不同路径 ||
- 状态表示
dp[i][j]表示到i, j 位置有多少种路径 - 状态转移方程
如果是障碍物，不需要处理这个节点位置，
- 初始化
初始化，仍然采用辅助节点的方式
- 填表
从上到下，从左到右 - 返回值
AC代码：
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); dp[0][1] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (obstacleGrid[i - 1][j - 1] == 0) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m][n]; } };
3. 礼物的最大价值
- 状态表示
dp[i][j]表示到i， j位置时最大的价值 - 状态转移方程
- 初始化
仍然采用虚拟节点的方法，来初始化。这里只需要将虚拟节点里面的值都初始化为0即可 - 填表
从上到下，从左到右 - 返回值
AC代码：
class Solution { public: int maxValue(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]; } } return dp[m][n]; } };
4. 下降最小和
- 状态表示
dp[i][j]表示到i， j 位置时的最小和 - 状态转移方程
- 初始化
这里虚拟节点，需要加一行再加上两列 - 填表
从上往下，从左到右 - 返回值
最后一行的最小值
AC代码：
class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { int m = matrix.size(); vector<vector<int>> dp(m + 1, vector<int>(m + 2, INT_MAX)); for (int j = 0; j < m + 2; j++) { dp[0][j] = 0; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1]; } } int ret = INT_MAX; for (int j = 1; j <= m; j++) { ret = min(ret, dp[m][j]); } return ret; } };
5. 最小路径和
- 状态表示
dp[i][j]表示i， j 位置时，最小的路径和 - 状态转移方程
- 初始化
虚拟节点，方便初始化 - 填表
- 返回值
AC代码：
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]; } };
6. 地下城游戏
- 状态表示
如果当以i, j 位置结尾所需的最低健康点数，为状态表示的时候，后面的节点也会影响这个节点的值。所以以某个位置为结尾的时候不能很好的解决这个题目。换一个状态表示：
如果以i, j为开始到达终点的所需健康点数，就可以很好的解决这个题目 - 状态转移方程
dp[i][j] + d[i][j] >= dp[i][j + 1]，需要注意的是当是一个负数的时候需要改为1
- 初始化
- 填表
从下往上，从右到左 - 返回值
AC代码：
class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int m = dungeon.size(), n = dungeon[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); dp[m][n- 1] = dp[m- 1][n] = 1; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]; dp[i][j] = max(1, dp[i][j]); } } return dp[0][0]; } };
