【算法挨揍日记】day19——62. 不同路径、63. 不同路径 II

ゝ一世哀愁。 2024-02-20 10:38 64阅读 0赞

## 62. 不同路径 ##

[62. 不同路径][62.]

### 题目描述： ###

一个机器人位于一个 `m x n`网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？![ac39175ef76a4bae91347e5a87c71c3c.png][]

### 解题思路： ###

> 状态表示：dp\[i\]\[j\]表示在到达（i，j）位置后，路线的总数
> 
> 状态转移方程：
> 
> dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\];
> 
> 初始化：
> 
> 因为我们从（1,1位置开始遍历，我们要保证1,1位置的值要为1），因此我们需要将（0,1）位置设为1，来满足状态转移方程
> 
> 填表顺序：左到右
> 
> 返回值：dp【m】【n】

### 解题代码： ###

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];
        }
    };

--------------------

### 63. 不同路径 II ###

[63. 不同路径 II][63. _ II]

### 题目描述： ###

一个机器人位于一个 `m x n` 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。

![8c8f799df62149df9bb6329554051520.png][]

### 解题思路： ###

> 状态表示： dp\[i\]\[j\]在到达（i，j）后，路线的总数
> 
> 状态转移方程：当ob（i-1，j-1）等于0的时候，如果向下向右的可以的话，ob（i-1，j-1）就为0，为1的话就没有意义了
> 
> 初始化：
> 
> dp【0】【1】=1
> 
> 填表顺序：从左到右
> 
> 返回值：dp【m】【n】；

### 解题代码： ###

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

[62.]: https://leetcode.cn/problems/unique-paths/
[ac39175ef76a4bae91347e5a87c71c3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/5f01a8feb3694a8684bffae353dbbe87.png
[63. _ II]: https://leetcode.cn/problems/unique-paths-ii/
[8c8f799df62149df9bb6329554051520.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/95ad02e0be144c63bd615f7cefa56997.png