算法练习-day32

动态规划

62. 不同路径

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

实例：

思路：本题我们已知机器人只能走右和下两种方向，因此我们就可以得出区域的上方和下方都只有一种走法。我们先创建一个二维数组dp，用于存储走法。先初始化二维数组，将0下标的全部走法设置为1，然后其他位置的走法数量等于上方数量+左方数量，最终返回目标位置

C++代码：

    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<n;i++)//这两个for循环就相当于初始化，区域的左边和上边只有一种可能，因此都是1
        {
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++)
        {
            dp[i][0]=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

题意：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

实例：

思路：本题和上一题的代码几乎一模一样，只是在方法数量的累加和初始化方面多加了一些限制。

首先是初始化方面，如果我们在初始化过程中遇到了障碍物，那么该位置以及之后的位置都无法走到，即方法为0。其次是其他位置的累加方面，如果该位置有障碍物就不能进行方法的累加了，这样也可以避免累加到障碍物的情况，非常的简单

C++代码：

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i<n; i++)
        {
            dp[0][i] = 1;
            if(obstacleGrid[0][i] == 1)//这里多加了一个条件，如果初始化遇到障碍，那么该位置及之后位置的元素都无法走到，全部设为0
            {
                while (i < n)
                {
                    dp[0][i] = 0;
                    i++;
                }
            }
        }
        for (int i = 0; i<m; i++)
        {
            dp[i][0] = 1;
            if(obstacleGrid[i][0] == 1)
            {
                while (i < m)
                {
                    dp[i][0] = 0;
                    i++;
                }
            }
        }
        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];
    }