【代码随想录练习营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70,
【代码随想录练习营】【Day 41】【动态规划-1 and 2】| Leetcode 509, 70, 746, 62, 63需强化知识点
标题
509. 斐波那契数
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
dp = * (n+1)
dp, dp = 0, 1
for i in range(2, n+1):
dp = dp + dp
return dp
70. 爬楼梯
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
dp = * n
dp, dp = 1, 2
for i in range(2, n):
dp = dp + dp
return dp
746. 使用最小花费爬楼梯
class Solution:
def minCostClimbingStairs(self, cost: List) -> int:
# 爬上台阶 i 所需支付的费用
dp = * (len(cost)+1)
for i in range(2, len(cost)+1):
dp = min(dp+cost, dp+cost)
return dp
62. 不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [ * n for _ in range(m)]
for i in range(m):
dp = 1
for i in range(n):
dp = 1
for i in range(1, m):
for j in range(1, n):
dp = dp + dp
return dp
63. 不同路径 II
[*]注意初始化和遍历时，碰到障碍物的处理
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List]) -> int:
m, n = len(obstacleGrid), len(obstacleGrid)
dp = [ * n for _ in range(m)]
for i in range(m):
if obstacleGrid == 1:
break
dp = 1
for i in range(n):
if obstacleGrid == 1:
break
dp = 1
for i in range(1, m):
for j in range(1, n):
if obstacleGrid == 1:
continue
dp = dp + dp
return dp
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]