【代码随想录练习营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70, ...

【代码随想录练习营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70, 746, 62, 63
需强化知识点

标题

509. 斐波那契数

1. class Solution:
2.     def fib(self, n: int) -> int:
3.         if n == 0:
4.             return 0
5.         if n == 1:
6.             return 1
7.         dp = [0] * (n+1)
8.         dp[0], dp[1] = 0, 1
10.         for i in range(2, n+1):
11.             dp[i] = dp[i-1] + dp[i-2]
12.         
13.         return dp[n]

复制代码

70. 爬楼梯

1. class Solution:
2.     def climbStairs(self, n: int) -> int:
3.         if n == 1:
4.             return 1
5.         if n == 2:
6.             return 2
7.         dp = [1] * n
8.         dp[0], dp[1] = 1, 2
10.         for i in range(2, n):
11.             dp[i] = dp[i-1] + dp[i-2]
12.         
13.         return dp[n-1]

复制代码

746. 使用最小花费爬楼梯

1. class Solution:
2.     def minCostClimbingStairs(self, cost: List[int]) -> int:
4.         # 爬上台阶 i 所需支付的费用
5.         dp = [0] * (len(cost)+1)
6.         
7.         for i in range(2, len(cost)+1):
8.             dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
9.         
10.         return dp[len(cost)]         

复制代码

62. 不同路径

1. class Solution:
2.     def uniquePaths(self, m: int, n: int) -> int:
3.         dp = [[0] * n for _ in range(m)]
5.         for i in range(m):
6.             dp[i][0] = 1
7.         for i in range(n):
8.             dp[0][i] = 1
9.         
10.         for i in range(1, m):
11.             for j in range(1, n):
12.                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
13.         
14.         return dp[m-1][n-1]      

复制代码

63. 不同路径 II

• 注意初始化和遍历时，碰到障碍物的处理
  

1. class Solution:
2.     def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
3.         m, n = len(obstacleGrid), len(obstacleGrid[0])
4.         dp = [[0] * n for _ in range(m)]
6.         for i in range(m):
7.             if obstacleGrid[i][0] == 1:
8.                 break
9.             dp[i][0] = 1
10.         
11.         for i in range(n):
12.             if obstacleGrid[0][i] == 1:
13.                 break
14.             dp[0][i] = 1
15.         
16.         for i in range(1, m):
17.             for j in range(1, n):
18.                 if obstacleGrid[i][j] == 1:
19.                     continue
20.                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
21.         
22.         return dp[m-1][n-1]         

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。