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

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]

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]

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)]          

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]       

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

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]