动态规划两题连刷，移动下标的小技巧

Unique Paths II

样例

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

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]


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.

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]