本文主要是介绍【代码随想录训练营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70, 746, 62, 63，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【代码随想录训练营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70, 746, 62, 63
需强化知识点
题目
509. 斐波那契数
class Solution:def fib(self, n: int) -> int:if n == 0:return 0if n == 1:return 1dp = [0] * (n+1)dp[0], dp[1] = 0, 1for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]
70. 爬楼梯
class Solution:def climbStairs(self, n: int) -> int:if n == 1:return 1if n == 2:return 2dp = [1] * ndp[0], dp[1] = 1, 2for i in range(2, n):dp[i] = dp[i-1] + dp[i-2]return dp[n-1]746. 使用最小花费爬楼梯
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:# 爬上台阶 i 所需支付的费用dp = [0] * (len(cost)+1)for i in range(2, len(cost)+1):dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])return dp[len(cost)]
62. 不同路径
class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0] * n for _ in range(m)]for i in range(m):dp[i][0] = 1for i in range(n):dp[0][i] = 1for 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]
63. 不同路径 II
- 注意初始化和遍历时，遇到障碍物的处理
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]for i in range(m):if obstacleGrid[i][0] == 1:breakdp[i][0] = 1for i in range(n):if obstacleGrid[0][i] == 1:breakdp[0][i] = 1for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] == 1:continuedp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[m-1][n-1]
这篇关于【代码随想录训练营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70, 746, 62, 63的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
