本文主要是介绍代码随想录算法训练营Day 39| 动态规划part02 | 62.不同路径、63. 不同路径 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录算法训练营Day 39| 动态规划part02 | 62.不同路径、63. 不同路径 II
文章目录
- 代码随想录算法训练营Day 39| 动态规划part02 | 62.不同路径、63. 不同路径 II
- 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]=1for 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 1return 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]=1else:breakfor j in range(n):if obstacleGrid[0][j]==0:dp[0][j]=1else:breakfor 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:continuereturn dp[m-1][n-1]
这篇关于代码随想录算法训练营Day 39| 动态规划part02 | 62.不同路径、63. 不同路径 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!