代码随想录day34dp2

62.不同路径

题目链接
文章讲解

class Solution {
public:int uniquePaths(int m, int n) {// 1. 确定 DP 数组及下标的含义：//    dp[i][j] 表示从 (0, 0) 到 (i, j) 的不同路径数。//    即 dp[i][j] 记录了到达位置 (i, j) 的所有路径数。int dp[m][n];  // 创建一个二维数组 dp 来存储路径数// 2. 确定递推公式：//    递推公式为 dp[i][j] = dp[i-1][j] + dp[i][j-1]//    即到达当前位置 (i, j) 的路径数等于从上面位置 (i-1, j) 和左边位置 (i, j-1) 的路径数之和。// 3. DP 数组如何初始化：//    - dp[0][i] = 1 表示第一行的所有格子只能从左边走来（只有一种路径）。//    - dp[i][0] = 1 表示第一列的所有格子只能从上面走来（只有一种路径）。for (int i = 0; i < n; i++) {dp[0][i] = 1;  // 第一行所有格子路径数为 1}for (int i = 0; i < m; i++) {dp[i][0] = 1;  // 第一列所有格子路径数为 1}// 4. 确定遍历顺序：//    从 (1, 1) 开始遍历整个 dp 数组，更新每个格子到达的路径数。//    每个格子 dp[i][j] 由它上方的格子 dp[i-1][j] 和左方的格子 dp[i][j-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];  // 根据递推公式计算路径数}}// 5. 举例推导 DP 数组：//    假设 m = 3, n = 3//    初始状态：dp 数组为：//    [1, 1, 1]//    [1, 0, 0]//    [1, 0, 0]//    填充 dp 数组：//    dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2//    dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3//    dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3//    dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6//    最终 dp 数组为：//    [1, 1, 1]//    [1, 2, 3]//    [1, 3, 6]//    返回 dp[2][2] = 6，表示从左上角到右下角的路径数为 6 条。return dp[m-1][n-1];  // 返回到达右下角的路径数}
};

63. 不同路径 II

题目链接
文章讲解

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {// 1. 确定 DP 数组及下标的含义：//    dp[i][j] 表示到达 (i, j) 位置的不同路径数。//    (i, j) 位置的路径数等于从上方格子 (i-1, j) 和左方格子 (i, j-1) 的路径数之和。int m = obstacleGrid.size();  // 行数int n = obstacleGrid[0].size();  // 列数int dp[m][n];  // 创建一个二维 DP 数组来存储路径数// 2. 确定递推公式：//    dp[i][j] = dp[i-1][j] + dp[i][j-1]  (如果当前位置没有障碍物)//    如果当前位置有障碍物，dp[i][j] = 0。//    递推的过程是从 (0, 0) 开始计算每个位置的路径数。memset(dp, 0, sizeof(dp));  // 初始化 dp 数组，默认值为 0// 3. DP 数组如何初始化：//    - dp[0][0] 已初始化为 0，表示起始位置的路径数。//    - 第一列和第一行的路径数依赖于障碍物的情况，障碍物会将其路径数置为 0。// 初始化第一列for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1) break;  // 如果第一列遇到障碍物，后续路径数为 0dp[i][0] = 1;  // 如果没有障碍物，路径数为 1}// 初始化第一行for (int i = 0; i < n; i++) {if (obstacleGrid[0][i] == 1) break;  // 如果第一行遇到障碍物，后续路径数为 0dp[0][i] = 1;  // 如果没有障碍物，路径数为 1}// 4. 确定遍历顺序：//    从 dp[1][1] 开始，逐个填充 dp 数组，根据递推公式更新每个格子的路径数。//    当前格子的路径数依赖于上方和左方格子的路径数。for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0;  // 当前格子是障碍物，路径数为 0} else {dp[i][j] = dp[i][j - 1] + dp[i - 1][j];  // 当前格子的路径数等于从左方和上方的路径数之和}}}// 5. 举例推导 DP 数组：//    假设 obstacleGrid = [//        [0, 0, 0],//        [0, 1, 0],//        [0, 0, 0]//    ]//    dp 数组初始化为：//    dp[0][0] = 1//    dp[0][1] = 1//    dp[0][2] = 1//    dp[1][0] = 1//    dp[1][1] = 0  (因为有障碍物)//    dp[1][2] = 1//    dp[2][0] = 1//    dp[2][1] = 1//    dp[2][2] = dp[2][1] + dp[1][2] = 1 + 1 = 2//    最终 dp 数组为：//    [//        [1, 1, 1],//        [1, 0, 1],//        [1, 1, 2]//    ]//    返回 dp[2][2] = 2，表示从左上角到右下角的不同路径数有 2 条。// 返回结果：dp[m-1][n-1] 表示到达终点 (m-1, n-1) 的路径数return dp[m - 1][n - 1];}
};