代码随想录算法训练营Day39 | 62.不同路径、63. 不同路径 II

62.不同路径

思路比较简单，因为机器人只能向右和向下走，所以走到一个格子的方法等于到达其上方格子的方法加上到达其左方格子的方法

1、DP数组定义：二维DP数组，dp[i][j]表示到达行 i 列 j 格子的方法数

2、DP数组初始化：首行和首列元素初始化为1，其他元素随意

3、递推公式：走到一个格子即走到其上方格子再向下走一步，或走到其左方格子再向右走一步，所以：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

4、遍历顺序：因为是向右、向下走，所以从上往下、从左向右遍历

int uniquePaths(int m, int n) {
	// dp[i][j]数组表示到达该格子的方法数，首行和首列元素初始化为1
	vector<vector<int>> dp(n, vector<int>(m, 1));
 
	// 从上往下、从左向右遍历
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < m; ++j) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[n - 1][m - 1];
}

63. 不同路径 II

与62不同路径主要思路一样，差别主要在于初始化以及递推处的分支处理

DP数组初始化：首行与首列如果出现障碍物，其后的行/列都初始化为0，否则初始化为1

递推公式：有障碍时dp[i][j]设置为0（一方面表示没有方法能到达该格子，一方面表示无法从该格子出发向右或向下到达其他格子），否则dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int n = obstacleGrid.size();
	int m = obstacleGrid[0].size();
	vector<vector<int>> dp(n, vector<int>(m, 1));
	// 首行与首列如果出现障碍物，其后的行/列都初始化为0，否则初始化为1
	bool isObstructed = false;
	for (int i = 0; i < n; ++i) {
		if (obstacleGrid[i][0] == 1) isObstructed = true;
		if (isObstructed) dp[i][0] = 0;
	}
	isObstructed = false;
	for (int j = 0; j < m; ++j) {
		if (obstacleGrid[0][j] == 1) isObstructed = true;
		if (isObstructed) dp[0][j] = 0;
	}
 
	// 从上往下、从左向右遍历
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < m; ++j) {
			// 有障碍时dp[i][j]设置为0
			dp[i][j] = obstacleGrid[i][j] ? 0 : dp[i - 1][j] + dp[i][j - 1];
		}
	}
 
	return dp[n - 1][m - 1];
}

好像有点感觉了，大致思路就是从题意中获取状态转移方法，遍历顺序和状态转移的过程也存在一定关系