代码随机化算法训练营第 32 天

62. 不同路径

这道题自己思考ac出来了，主要是这道题需要使用二维的dp数组进行规划，由于动归是递推的，所以从结果向前思考，因此到右下角的方法只能由右下角这个格子或者左边这个格子走过来，因此右下角这个格子的方法数应该等于上一个格子的方法数加上左边这个格子的方法数。这就是递推的过程。值得注意的是只有一行的或者一列的每个格子都只有1种方法，还有就是多行多列的边界格子也是只有一种方法，这个也是要初始化的。自己写的代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        if (m == 1 || n == 1) return 1;
        dp[0][0] = 0;
        dp[0][1] = 1;
        dp[1][0] = 1;
        for (int i = 0; i < m; i++) {
            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];

    }
};

63. 不同路径 II

这道题比上道题只不过多了个障碍物，在初始化的时候和递推的要注意障碍物的处理就行了 

首先几个特殊情况 当障碍物在起点或者终点的话直接返回0；

然后初始化边界的时候在障碍物之前的都初始化为1，障碍物以及障碍物之后的都初始化为0 ；

接着循环过程中发现上个或左边的有障碍物的话使用0代替原来的方法数；完整代码如下：

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