力扣算法刷题Day39｜动态规划：不同路径 I&II-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣算法刷题Day39｜动态规划：不同路径 I&II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣题目：#62.不同路径

刷题时长：参考题解后10min

解题方法：动规

复杂度分析

问题总结

本题收获文章来源地址https://www.toymoban.com/news/detail-532649.html

动规思路
- 确定dp数组及下标的含义：dp[i][j] 表示从（0，0）出发，到(i, j) 有dp[i][j]条不同的路径
- 确定递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- dp数组的初始化：题目说只能往下或往右走，所以dp[i][0]都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条。dp[0][j]同理都初始化为1
- 确定遍历顺序：dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的

力扣题目：#63. 不同路径 II

刷题时长：30min

解题方法：动规

复杂度分析

问题总结

本题收获

dp数组初始化：一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理。因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。

到了这里，关于力扣算法刷题Day39｜动态规划：不同路径 I&II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！