动态规划 Leetcode 63 不同路径II

不同路径II

Leetcode 63

学习记录自代码随想录

要点：1.需要想到几个特殊输入，起始和末尾位置有障碍则直接返回0；
2.初始化dp数组时需要想到dp[i][0]=1，dp[0][j]=1，但是如果首行首列某个点为障碍则其后面点均无法达到dp数组在这些点为0，障碍点处无法达到dp数组在障碍点为0；

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        
        if(obstacleGrid[m-1][n-1] || obstacleGrid[0][0]) return 0;
        if(m == 1 || n == 1) return 1;
        
        // 1.dp[i][j]代表到达（i，j）有多少天路径
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // 2.递推公式dp[i][j] = dp[i-1][j] + dp[i][j-1]
        // 3.dp数组初始化, dp[i][0] = 1, dp[0][j] = 1, 首行首列中（一旦发现有障碍，则其后面格子均无法到达） 
        // dp[i][j] = 0（(i，j)为障碍）
        for(int i = 0; i < m; i++){
            if(obstacleGrid[i][0]){
                break;
            }else{
                dp[i][0] = 1;
            }
        }
        for(int j = 0; j < n; j++){
            if(obstacleGrid[0][j]){
                break;
            }else{
                dp[0][j] = 1;
            }
        }
        // 这块和下面判断重复，因为数组数组初值已经设为0
        // for(int i = 1; i < m; i++){
        //     for(int j = 1; j < n; j++){
        //         if(obstacleGrid[i][j]) dp[i][j] = 0;
        //     }
        // }
        // 4.遍历顺序从左到右，从上到下
        // 有i-1记得i，j从1开始
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(!obstacleGrid[i][j]){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        // 5.举例推导dp数组
        return dp[m-1][n-1];
    }
};

原文地址：https://blog.csdn.net/weixin_46930685/article/details/136638962

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！