代码随想录算法训练营Day 39| 动态规划part02 | 62.不同路径、63. 不同路径 II
62.不同路径
- 确定dp数组以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。- 确定递推公式
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]
状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];- dp数组如何初始化
dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理;
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;- 确定遍历顺序
看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。- 打印dp数组
一、动态规划
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
# 创建dp数组：用于存储唯一路径数
dp=[[0]*n for _ in range(m)]
#初始化：设置第一行和第一列的基本情况
for i in range(m):
dp[i][0]=1
for j in range(n):
dp[0][j]=1
# 递推：计算每个单元格的唯一路径数
for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[m-1][n-1]
二、递归
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m ==1 or n ==1:
return 1
return self.uniquePaths(m-1, n)+self.uniquePaths(m,n-1)
63. 不同路径 II
只要考虑到，遇到障碍dp[i][j]保持0就可以了。
也有一些小细节，例如：初始化的部分，很容易忽略了障碍之后应该都是0的情况。
一、动态规划
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0]*n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0]==0:
dp[i][0]=1
else:
break
for j in range(n):
if obstacleGrid[0][j]==0:
dp[0][j]=1
else:
break
for i in range(1,m):
for j in range(1,n):
if obstacleGrid[i][j] ==0:
dp[i][j] = dp[i-1][j]+dp[i][j-1]
else:
continue
return dp[m-1][n-1]
