DP(动态规划)经典路径问题 | LeetCode
一定要认真看完这篇文章✌
大树不敢保证看完你就可掌握动态规划，但是，你一定可以 AC 动态规划中的路径问题！！😉
由于篇幅限制也为了不让大家产生阅读疲劳，980. 不同路径 III 这道题目会单独写一篇作为路径问题的收尾篇。
动态规划中的路径问题，题目来自于 LeetCode，子标题为 题号 名称 的格式。
62 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下 向右 -> 向下 -> 向右 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3 输出: 28
提示：
-
1 <= m, n <= 100 -
题目数据保证答案小于等于 2 * 10 ^ 9
根据移动规则，我们可以确定，在 [i, j] 位置的点，只能通过 [i-1, j] 以及 [i, j-1] 到达
由以上分析，我们可以写出 solution 代码
Solution
class Solution {
public int uniquePaths(int m, int n) {
// 定义dp数组，数组中的值代表到达该位置的路径数目
int[][] dp = new int[m][n];
// 初始化第一行&第一列数值，因为只能向下和向右，所以值默认为1
for(int i = 0; i < m; i++){
dp[i][0] = 1;
}
for(int j = 0; j < n; j++){
dp[0][j] = 1;
}
// 根据移动规则，我们可以确定，在 [i, j] 位置的点，只能通过 [i-1, j] 以及 [i, j-1] 到达
// 所以 dp[i][j] = dp[i-1][j] + dp[i][j-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];
}
}
对于该解决方案，其时间复杂度与空间复杂度为：
-
时间复杂度：O(m * n) -
空间复杂度：O(m * n)
我们知道，通常对于DP题目的初始解法，是可以对其空间复杂度进行优化的，比如这道题目，我们刚开始用了二维数组来存储，所以消耗空间为 O(m * n) 但我们完全可以压缩为一维数组存储，下面我们就来尝试实现一下。
-
依然记得，规则：路径数 （i,j) = （i-1,j) + （i, j-1)
Solution·space-optimization
class Solution {
public int uniquePaths(int m, int n) {
int[] result = new int[m];
// 初始化首行信息
for(int i = 0; i < m; i++) result[i] = 1;
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
// 更新数组，当前位置 = 更新后的左侧 + 更新前的上一位
result[j] += result[j-1];
}
}
return result[m-1];
}
}
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明： m 和 n 的值均不超过 100。
示例 1:
输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 -> 向右
对于 不同路径 II 该题我们可以发现，相对于第一题，多了一个限制条件 考虑网格中有障碍物，那这个条件对于我们解决该题而言有什么含义呢？
-
这个点无法到达 -> 到达的路径为 0
所以我们对这个条件进行限定后就转变为同第一题相同的问题了。
Solution
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid == null){
return 0;
}
int nr = obstacleGrid.length, nc = obstacleGrid[0].length;
int[][] dp = new int[nr][nc];
// 初始化边界条件
for(int r = 0; r < nr; r++){
// 若该边界为1，即障碍物，则之后的点均不可达，直接break
if(obstacleGrid[r][0] == 1) break;
dp[r][0] = 1;
}
for(int c = 0; c < nc; c++){
if(obstacleGrid[0][c] == 1) break;
dp[0][c] = 1;
}
// 循环填充内部数据
for(int r = 1; r < nr; r++){
for(int c = 1; c < nc; c++){
if(obstacleGrid[r][c] == 1) {
// 障碍物，不可到达，所以直接填写为 0
dp[r][c] = 0;
continue;
}
dp[r][c] = dp[r-1][c] + dp[r][c-1];
}
}
return dp[nr-1][nc-1];
}
}
✌ Kill 掉该题了
对于该解决方案，其时间复杂度与空间复杂度同第一题优化前的解法相同。
好，下边我们来进行一下优化，这个dp的优化呢，我们就不再去做将 O(m*n) 优化到 O(m) 的空间优化了。我们可以直接将其进行原地的dp，优化到 O(1）的时间复杂度。
注意了！ 😎
根据题目中传递的参数，我们可以发现，它本身就是一个二维数组，所以我们设想在它自身进行计数，从而省去空间上的消耗。
Solution·space-optimization
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid == null || obstacleGrid[0][0] == 1){
// 若左上角为障碍物，直接返回0
return 0;
}
int nr = obstacleGrid.length, nc = obstacleGrid[0].length;
// 初始化边界条件
for(int r = 0; r < nr; r++){
if(obstacleGrid[r][0] == 1){
for(int i = r; i < nr; i++){
// 如果发现一个1，则将后续全部置为0
obstacleGrid[i][0] = 0;
}
break;
}
obstacleGrid[r][0] = 1;
}
for(int c = 1; c < nc; c++){
// 注意这里的 c 初始为 1， 大家可以考虑下为什么？
if(obstacleGrid[0][c] == 1) {
for(int j = c; j < nc; j++){
obstacleGrid[0][j] = 0;
}
break;
}
obstacleGrid[0][c] = 1;
}
// 循环填充内部数据
for(int r = 1; r < nr; r++){
for(int c = 1; c < nc; c++){
if(obstacleGrid[r][c] == 1) {
obstacleGrid[r][c] = 0;
continue;
}
obstacleGrid[r][c] = obstacleGrid[r-1][c] + obstacleGrid[r][c-1];
}
}
return obstacleGrid[nr-1][nc-1];
}
}
可以看到，在上边代码中，初始化首列时的初始条件为 int c = 1; c < nc; c++，为什么是从1开始呢？
其实是因为我们在初始化行的时候，将 obstacleGrid[0][0] 的位置置为了 1，所以如果我们在初始列时依旧从0开始就会将左上角的 1 看作为障碍物，从而无法到达。
但是因为在函数开始时，我们便进行了判断 if(obstacleGrid == null || obstacleGrid[0][0] == 1)，所以左上角的 1 必然是我们修改后的，而非障碍物。
经过这次优化，最终空间复杂度只有常量级别；在做题时候可以用，但是如果要用在实际环境中不建议直接对原数组进行修改哦~ 😉
如果你看到了这，恭喜你又读完了一篇文章！
至此本文已经逼近2000字了，为了保证不产生阅读疲倦，路径问题的最后一个 boss 980. 不同路径 III 这道题目会单独写一篇作为DP路径问题的完结篇。
点个在看吧 👇👇