数据结构与算法：动态规划dp：理论基础和相关力扣题（509.斐波那契数列、70.爬楼梯）

1.0.理论基础

动态规划主要解决的问题种类有：

• 背包问题
• 打家劫舍
• 股票问题
• 子序列问题

解决步骤：

• dp数组及其下标的意义
• 递推公式
• dp数组初始化
• 遍历顺序
• 打印dp数组

2.0.相关力扣题

509.斐波那契数列

class Solution:def fib(self, n: int) -> int:if n==0:return 0if n==1:return 1dp = [0]*35dp[1] = 1for i in range(2,31):dp[i] = dp[i-1]+dp[i-2]return dp[n]

效率：0ms，击败100.00%

状态压缩

再优化一下，因为每个斐波那契数只和它相邻的两个数有关，所以我们其实不需要存储三十多个长度，只需要保留2个数的信息即可。也就是状态压缩。

class Solution:def fib(self, n: int) -> int:if n==0:return 0if n==1:return 1dp = [0]*2dp[1]=1sum = 0for i in range(2,n):sum = dp[0]+dp[1]dp[0] = dp[1]dp[1] = sumreturn dp[0]+dp[1]

70.爬楼梯

跟509.斐波那契数列很像

class Solution:def climbStairs(self, n: int) -> int:if n==1:return 1if n==2:return 2dp = [0] * 50dp[1] = 1dp[2] = 2for i in range(3,n+1):dp[i] = dp[i-1]+dp[i-2]print(dp)return dp[n]

效率：0ms，击败100.00%

状态压缩

class Solution:def climbStairs(self, n: int) -> int:if n==1:return 1if n==2:return 2dp = [0] * 4dp[1] = 1dp[2] = 2sum = 0for i in range(3,n):sum = dp[1]+dp[2]dp[1] = dp[2]dp[2] = sumreturn dp[1]+dp[2]

756.使用最小代价爬楼梯

需要注意的是，这里的dp[i]代表着爬到台阶为i时所需的最小代价。

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost)if n == 2:return min(cost[0],cost[1])dp = [0]*1005dp[0] = 0dp[1] = 0for i in range(2,n+1):dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])return dp[n]

效率：2ms，击败83.69%