62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
#DFS
# 超时
def uniquepaths(m,n):
stack = []
stack.append([0,0])
count = 0
while stack:
x,y = stack.pop()
if (x,y) == (m-1,n-1):
count += 1
for dx,dy in ([1,0],[0,1]):
if x+dx < m and y+dy<n:
stack.append([x+dx,y+dy])
return count
# 排列组合
def uniquePaths(m,n):
import math
return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))
# 动态规划
def uniquePaths(m,n):
dp = [[0]*m for _ in range(n)]
for i in range(m):#第一行置一
dp[0][i] = 1
for i in range(n):#第一列置1
dp[i][0] = 1
for i in range(1,n):
for j in range(1,m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
# 动态规划
def minPathSum(grid):
m,n = len(grid[0]),len(grid)
dp = [[grid[0][0]]*m for _ in range(n)]
for i in range(1,m):#第一行
dp[0][i] = grid[0][i] + dp[0][i-1]
for i in range(1,n):#第一列
dp[i][0] = grid[i][0] + dp[i-1][0]
for i in range(1,n):
for j in range(1,m):
dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
return dp[-1][-1]
# 动态规划 在原数组操作
def minPathSum(grid):
m,n = len(grid[0]),len(grid)
for i in range(1,m):#第一行
grid[0][i] = grid[0][i] + grid[0][i-1]
for i in range(1,n):#第一列
grid[i][0] = grid[i][0] + grid[i-1][0]
for i in range(1,n):
for j in range(1,m):
grid[i][j] = min(grid[i-1][j],grid[i][j-1])+grid[i][j]
return grid[-1][-1]