LeetCode 63. 不同路径 II

63. 不同路径 II

思路：

动态规划
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径
根据题意，只能向下或者向右移动一步，则dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
但是，如果(i, j) 处有障碍，则dp[i][j] = 0
最后求得dp[n-1][m-1]即为从左上角到右下角路径数
注意：在对dp数组进行初始化时，如果遇到了障碍，那么在障碍位置上及之后位置上的dp值都应该为0

代码：

#include
#include
#include
#include
#include
using namespace std;

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int dp[105][105];
        memset(dp,0,sizeof(dp));
        // 行数
        int n=obstacleGrid.size();
        // 列数
        int m=obstacleGrid[0].size();
        for(int i=0; i<n; ++i)
            if(obstacleGrid[i][0]!=1)
                dp[i][0]=1;
            else
                break;
        for(int j=0; j<m; ++j)
            if(obstacleGrid[0][j]!=1)
                dp[0][j]=1;
            else
                break;
        for(int i=1; i<n; ++i)
            for(int j=1; j<m; ++j)
                if(obstacleGrid[i][j]!=1)
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[n-1][m-1];
    }
};


int main()
{
    vector<vector<int>> num={{1,0},{0,0}};
    Solution *solution=new Solution();
    int ans=solution->uniquePathsWithObstacles(num);
    printf("%d\n",ans);
    delete(solution);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

总结：刚开始写这道题时，在对dp数组进行初始化时没有考虑到障碍之后就没路了...（在此记录）