代码随想录第39天 | 动态规划part02

代码随想录算法训练营第39天 | 动态规划part02

● 62.不同路径
● 63. 不同路径 II

题目一 62.不同路径

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

• 输入：m = 2, n = 3
• 输出：3

本质上是高中的排列组合问题。只需总共走m - 1 + n - 1 步，其中一定有m - 1步向下， n - 1步向右。即从m + n - 2中选出m-1个数。
即 $C_{m+n?2}^{m?1}=C_{m+n?2}^{n?1}$ 步.因此本题可转化为计算组合数的问题。

求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};

使用深度优先搜索，复杂度非常高，容易超时。

使用动态规划如下：
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
初始化：最左一列和最上一行肯定为1，因为到达这些位置只有一种方法。
因此 dp[i][0] = dp[0][j] = 1;
递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

public int uniquePaths(int m, int n) 
{
	//
	int[][] dp = new int[m][n];
	for(int i=0; i<m; i++)
		dp[i][0] = 1;
	for(int j=0; j<n; j++)
		dp[0][j] = 1;
	for(int i=1; i<m; i++)//dp[m][n] = dp[m-1][n] + dp[m][n-1]
	{
		for(int j=1; j<n; j++)
		{
			dp[i][j] = dp[i-1][j] + dp[i][j-1];
		}
	}
	return dp[m-1][n-1];
}

• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)

在空间上甚至可以进一步优化：使用一个一维的滚动数组，后一个数值计算前面全部数值的和。
因为无论是向右还是向下，步数都只加一。

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

题目二 63. 不同路径 II

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

• 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
• 输出：2 解释：
• 3x3 网格的正中间有一个障碍物。
• 从左上角到右下角一共有 2 条不同的路径：
  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

本题有了障碍，方法就很有限了，最好使用动态规划。

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
初始化：最左一列和最上一行肯定为1，因为到达这些位置只有一种方法。
因此 dp[i][0] = dp[0][j] = 1;

关键的一点：有了障碍，应当初始化为0.
因此动态规划应当在没有障碍的位置推导。

public int uniquePathsWithObstacles(int[][] obstacleGrid) 
{
	int m = obstacleGrid.length;
	int n = obstacleGrid[0].length;
	if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)//开始和结束有障碍
		return 0;
	int[][] dp = new int[m][n];
	for(int i=0; i<m && obstacleGrid[i][0] == 0; i++)
		dp[i][0] = 1;
	for(int j=0; j<n && obstacleGrid[0][j] == 0; j++)
		dp[0][j] = 1;
	for(int i=1; i<m; i++)
	{
		for(int j=1; j<n; j++)
		{
			if(obstacleGrid[i][j] == 1)//有障碍
				continue;
			dp[i][j] = dp[i-1][j] + dp[i][j-1];
		}
	}
	return dp[m-1][n-1];
}

• 时间复杂度：O(n × m)，n、m 分别为obstacleGrid 长度和宽度
• 空间复杂度：O(n × m)

同理可以在空间上优化为一维数组。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        if (obstacleGrid[0][0] == 1)
            return 0;
        vector<int> dp(obstacleGrid[0].size());
        for (int j = 0; j < dp.size(); ++j)
            if (obstacleGrid[0][j] == 1)
                dp[j] = 0;
            else if (j == 0)
                dp[j] = 1;
            else
                dp[j] = dp[j-1];

        for (int i = 1; i < obstacleGrid.size(); ++i)
            for (int j = 0; j < dp.size(); ++j){
                if (obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else if (j != 0)
                    dp[j] = dp[j] + dp[j-1];
            }
        return dp.back();
    }
};

本题的关键是考虑对有障碍时的位置的处理。