Leetcode-不同路径Ⅰ Ⅱ（中等）

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

动态规划

题目问总共有多少条不同的路径？所以dp[i][j]表示到达(i,j)点时的路径条数；
dp[i][j]=dp[i-1][j]+dp[i][j-1] 所以到达该点的路径等于左边点的路径+上边点的路径和
需要注意的是左边界和右边界，路径只有一条

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(2, vector<int>(n,0));
        for(int i=0;i<m;i++)//从0开始的，所以到m-1结束
            dp[i][0]=1;
        for(int i=0;i<n;i++)
            dp[0][i]=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-1][n-1];  
    }

};

优化

具体参考leetcode题解

对于每个点，只需要知道该行和上一行就可以了，所以只留下两行
第三行的时候覆盖第一行，次数所需要的的上一点的数据就变成了了下一点，所以(i-1)%2 取余 使得结果都在这两行内
交替使用
程序上也就是把前一个程序的所以行i变成了i%2 i-1变成(i-1)%2

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

};

不同路径Ⅱ

现在考虑网格中有障碍物。网格中的障碍物和空位置分别用 1 和 0 来表示。

思路：
有炸弹的话，表示当前的路是不可行的，走不通的
所以加一种情况
不为炸弹时：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
为炸弹时：dp[i][j] = 0
可以将二维数组初始化为全0，只有非炸弹情况才填充
注意：：：对于最上一行和最左一列，如果出现一个炸弹，后面全为0!!!!!!

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) //如有一个炸弹，下边全都不能走
                break;
            else dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) //如有一个炸弹，后边全都不能走
                break;
            else dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) //非炸弹才计算，是炸弹时默认0
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};