LeetCode 63、64 动态规划两题连刷，移动坐标的小技巧

今天是LeetCode的37篇，趁着周末，开始我们愉快的刷题。今天要刷的题目是LeetCode 63和64两题，分别是Unique Paths II和Minimum Path Sum。

从题目的名称我们就可以看出来，今天的题目都和path有关，其实不止如此，这两题的题意也几乎一样，本质上都是上一篇文章所讲的LeetCode 62题的延伸和拓展。这也是我们把这两题放在一起解决的原因。

Unique Paths II

我们先来看第一题，Unique Paths II。它和62题基本一样，都是机器人走一个矩形迷宫求解路径总数的问题。大概就像是下面这张图一样，机器人从左上角出发，往右下角前进。

机器人只能往下或者是往右移动，不能往左或者是往上。并且这一次给定的矩形迷宫不再是所有点都可以访问了，有些点设置了路障。机器人不能访问设置了路障的点，请问在此情况下，机器人从起点走到终点的路径一共有多少条？

样例

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

从样例可以看出来，题目用一个二维数组代表了矩形，数组当中为1的点表示了路障。

如果你读过我们上一篇文章，做过LeetCode 62题，你会发现这题几乎是完全一样的翻版，并且连解题思路都一样。如果你没有做过，可以通过下面的传送门回顾一下：

LeetCode 62: 想到动态规划就无敌了？这道题还有更牛的解法

我们套用一下62题的思路，其中动态规划的解法是完全适用的。路障的存在只会影响路障的点本身以及它附近可以转移到的点，对于它本身而言，它无法到达，自然可访问的路径数就是0。而对于它转移到的点来说，这点无法访问，自然贡献也是0。所以我们只需要在转移的过程当中将路障的位置置为0即可。

而通过排列组合求解答案的方法就无法使用了，因为路障和路障之间会有影响，所以我们没有办法仅仅通过排列组合就求出起点到路障处的路径数量，也无法确定这个路障对于总体路径数量带来的变化量，更无法确定路障是否有把所有通路堵死。这些点之间互相影响，仅仅通过数学很难计算，所以不太方便使用。

所以我们只能通过动态规划来求解，这段代码和上一题的几乎也一样，只不过做了一点细微的改动，加上了路障的判断。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n, m = len(obstacleGrid), len(obstacleGrid[0])
        # 我们维护的下标i从1到n，j从1到m
        dp = [[0 for _ in range(m+2)] for _ in range(n+2)]
        
        dp[0][1] = 1
        for i in range(1, n+1):
            for j in range(1, m+1):
               # 判断当前位置是否可达，由于下标范围不一致，所以要-1
                if obstacleGrid[i-1][j-1] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n][m]

这题看着简单，代码想要一次性写对不容易，有一个坑点是我们dp数组维护的下标范围和题目给定的路障数组的下标是不一样的，我们设置了下标从1开始，这样可以不用考虑转移时数组越界的问题。既然下标设置从1开始，我们在判断对应位置是否是路障的时候，就需要i和j都-1。

我们继续看下一题。

Minimum Path Sum

题意同样是机器人走矩形迷宫，不过稍有不同的是，这一题当中加上了路径长度的设置，我们从起点开始，每到一个点都会有一个消耗。现在我们想要让机器人从起点到达终点，所需要的最小消耗。

样例

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

如果你理解了上面一题的思路来做这题，几乎是秒杀的，因为解题的思路完全一样，只不过是我们dp数组当中维护不再是到每个点的路径数量，而是起点开始到这个点最小的距离。

对于每一个点i,j来说，它有两个来源，分别是i-1,j 和i, j-1。状态转移方程就是。这里的cost数组也就是题目给的每个点的花费。

我们直接来看代码：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        
        # 同样，我们dp维护的下标从1开始，初始化时赋值成无穷大
        dp = [[0x3f3f3f3f for _ in range(m+2)] for _ in range(n+2)]
        
        # 将0，1位置赋值成0，给(1, 1)提供一个消耗为0的入口
        dp[0][1] = 0
        
        for i in range(1, n+1):
            for j in range(1, m+1):
               # 由于下标从1开始，不用担心越界，无脑转移即可
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]
        
        return dp[n][m]

这里我们用了一个巧妙的方法，我们令，这是为了给一个消耗为0的入口。这样当我们执行的时候，就会获得0，这样就会自动完成，就不用我们在循环当中进行特判了。当然使用 if 特判也是可以的，但是这样写会更简洁一些。

结尾

到这里，关于LeetCode 63和64两题就做完了，是不是很轻松呢？

在这两题的代码当中我们用到了两个技巧，一个是为了防止dp的时候超界，而进行大量的判断，从而移动下标的技巧。另一个技巧是人为给初始位置提供一个初始选择入口的技巧。有了这两个技巧，可以大大简化我们编码的复杂度。不然你可能需要写很多额外的逻辑来特殊处理一些边界情况，这些边界情况往往复杂并且容易出错，因此能够避免是再好不过了。