062.Unique Paths I & II

Unique Paths 入门级动态规划，我一开始用递归做了一下，直接超时了//// 2333

二维数组动态规划

这里给机器人增加了障碍物，需要在递推式res[i][j]=res[i-1][j]+res[i][j-1]之前增加一个判断，

如果则res[i][j]=0，则res[i][j] = 0 (当然res初始化全部成0，所以可以直接跳过)

class Solution {
public:
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		int i, j, m = obstacleGrid.size(), n = obstacleGrid[0].size();
                // 默认所有地方都是堵着的
		vector<vector<int> > dp(m, vector<int>(n, 0));
		// 两头堵住了
		if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
			return 0;
		}
                //初始化动态规划矩阵dp
		for (i = 0; i < m&&obstacleGrid[i][0] == 0; i++) {
				dp[i][0] = 1;
		}
		for (j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
			dp[0][j] = 1;
		}
		for (i = 1; i < m; i++) {
			for (j = 1; j < n; j++) {
				if(obstacleGrid[i][j]==0)
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		return dp[m - 1][n - 1];

	}
};

一维数组

• 如果有阻碍，那么当前位置肯定是到达不了的，所以 dp[j] = 0
• 如果没有阻碍，那么到当前位置分为两个部分：上一行第j个 + 本行第j-1个

class Solution {
public:
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		vector<int> dp(obstacleGrid[0].size(), 0);

		for (int i = 0; i < obstacleGrid[0].size() && obstacleGrid[0][i] == 0; ++i)
		{
			dp[i] = 1;
		}

		for (int i = 1; i < obstacleGrid.size(); ++i)
		{
			if (obstacleGrid[i][0] == 1)
			{
				dp[0] = 0;
			}

			for (int j = 1; j < obstacleGrid[i].size(); ++j)
			{
				dp[j] = obstacleGrid[i][j] == 0 ? dp[j] + dp[j - 1] : 0;
			}
		}

		return dp.back();
	}
};

递归算法

本方法会超时

class Solution {
public:
	// 目前在第i行，第j列
	int uniquePaths(vector<vector<int>>& obstacleGrid, int i, int j) {
		if (i == obstacleGrid.size() - 1 && j == obstacleGrid[0].size() - 1 && obstacleGrid[i][j] == 0)
			return 1;
		if (i + 1 < obstacleGrid.size() && j + 1 < obstacleGrid[0].size() && obstacleGrid[i + 1][j] == 0 && obstacleGrid[i][j + 1] == 0)
			return uniquePaths(obstacleGrid, i + 1, j) + uniquePaths(obstacleGrid, i, j + 1);
		if (i + 1 < obstacleGrid.size() && obstacleGrid[i + 1][j] == 0)
			return uniquePaths(obstacleGrid, i + 1, j);
		if (j + 1 < obstacleGrid[0].size() && obstacleGrid[i][j + 1] == 0)
			return uniquePaths(obstacleGrid, i, j + 1);
		return 0;
	}
	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
		if (obstacleGrid[0][0] == 1)
			return 0;
		return uniquePaths(obstacleGrid, 0, 0);
	}
};

小结

看起来递归是最挫的方法，但是最好理解。

二维数组的方法其实也挺好理解的，一维数组感觉有点费解，不太显然的感觉。