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

2023-12-20 07:04:35

代码随想录算法训练营第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 \Large C_{m+n-2}^{m-1} = \Large C_{m+n-2}^{n-1} Cm+n?2m?1?=Cm+n?2n?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();
    }
};

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

文章来源:https://blog.csdn.net/techy649/article/details/135094457
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。