动态规划-不同路径问题

本篇是动态规划算法题目介绍的第二篇，如果对其他题目感兴趣的话，可以前往动态规划_Yuan_Source的博客-CSDN博客

不同路径Ⅰ

一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

解题思路

1. 定义状态：

   • 设 dp[i][j] 表示从左上角 (0, 0) 到达网格中 (i, j) 这个位置的不同路径数量。

2. 初始化状态：

   • 起始点 (0, 0) 显然只有一条路径到达，即 dp[0][0] = 1。
   • 第一行（i = 0）和第一列（j = 0）上的所有点都只有一条路径到达，因为它们只能通过向右或向下移动到达（取决于它们是行还是列）。因此，dp[0][j] = 1（对于所有 j），dp[i][0] = 1（对于所有 i）。

3. 状态转移方程：

   • 对于网格中的任意点 (i, j)（除了第一行和第一列），到达该点的路径数等于从上方 (i-1, j) 到达的路径数加上从左方 (i, j-1) 到达的路径数。即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

4. 计算顺序：

   • 由于每个点的路径数依赖于其上方和左方的点的路径数，因此我们需要从左上角开始，按行和列的顺序逐步计算到右下角。

5. 结果：

   • 最终，dp[m-1][n-1]（其中 m 和 n 分别是网格的行数和列数）将包含从左上角到右下角的不同路径数量。

class Solution {  
public:  
    int uniquePaths(int m, int n) {  
        vector<vector<int>> dp(m, vector<int>(n, 0));  
          
        // 初始化第一列  
        for (int i = 0; i < m; ++i) {  
            dp[i][0] = 1;  
        }  
          
        // 初始化第一行  
        for (int j = 0; j < n; ++j) {  
            dp[0][j] = 1;  
        }  
          
        // 填充dp表  
        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 - 1][n - 1];  
    }  
};

 这种方法将dp的第一行与第一列设为1

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp;
        dp.resize(m+1);
        for (int i = 0; i <= m; i++) {
            dp[i].resize(n+1);
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    if (j == 1) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 0;
                    }
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

dp的行数和列数都是m + 1和n + 1，这是因为我们需要考虑第0行和第0列的初始条件。在函数内部，我们首先初始化dp向量，将其所有元素初始化为0。然后，我们遍历dp向量的每个位置，根据当前位置的行数和列数更新路径数。

 不同路径Ⅱ

一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

 解题思路

1. 定义状态：

   • 设 dp[i][j] 表示从左上角 (0, 0) 到达网格中 (i, j) 这个位置（如果存在路径且该位置不是障碍物）的不同路径数量。

2. 初始化状态：

   • 如果起始点 (0, 0) 是障碍物（即 grid[0][0] == 1），则没有路径可以到达，直接返回 0。
   • 否则，初始化 dp[0][0] = 1（因为起始点自身算一条路径）。
   • 对于第一行（i = 0）和第一列（j = 0）上的点，如果它们不是障碍物，则路径数只能来自上方或左方（取决于它们是行还是列）。因此，对于非障碍物的点，dp[0][j]（j > 0）和 dp[i][0]（i > 0）应初始化为 1（如果它们不是障碍物）。

3. 状态转移方程：

   • 对于网格中的任意点 (i, j)（除了第一行和第一列），如果它不是障碍物，则到达该点的路径数等于从上方 (i-1, j) 到达的路径数加上从左方 (i, j-1) 到达的路径数。即 dp[i][j] = dp[i-1][j] + dp[i][j-1]（前提是这些位置不是障碍物）。
   • 如果 (i, j) 是障碍物，则 dp[i][j] = 0，因为无法到达该点。

4. 计算顺序：

   • 从左上角 (0, 0) 开始，按行和列的顺序逐步计算到右下角 (m-1, n-1)。

5. 结果：

   • 最终，dp[m-1][n-1] 将包含从左上角到右下角（如果存在路径）的不同路径数量。

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

        for (int j = 1; j <= n; ++j) {
            if (j == 1)
                dp[0][j] = 1;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (obstacleGrid[i - 1][j - 1] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }
};