LeetCode 509. 斐波那契数

70. 爬楼梯

746. 使用最小花费爬楼梯

感想

文档讲解：代码随想录

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区别于贪心，贪心没有状态推导，而是从局部直接选最优的。

解题步骤：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

为什么要先确定递推公式，然后在考虑初始化呢？因为一些情况是递推公式决定了dp数组要如何初始化！

做动规的题目，写代码之前一定要把状态转移在dp数组上的具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

题目类型有：基础题目、背包问题、打家劫舍、股票问题、子序列问题五大类

LeetCode 509. 斐波那契数

文档讲解：代码随想录

视频讲解：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili

状态：简单题，做对了，要注意特殊情况的处理，怎么返回

class Solution:def fib(self, n: int) -> int:if n == 0: # 边界条件return 0if n == 1:return 1dp = [0]*(n+1) # step1：dp数组 dp[i]是第i个斐波那契数的值dp[1] = 1 # step3：dp数组初始化for i in range(2, n+1): # step4：因为要用到前面的状态，所以遍历顺序从前向后dp[i] = dp[i-1] + dp[i-2] # step2：递推公式/状态转移方程return dp[n]

时间复杂度O(n)

空间复杂度O(n)

当前状态dp[i]只依赖前面两个状态dp[i-1]和dp[i-2]，所以可以不用维护一整个数组，而是3个量就可以了，得到上面程序的精简版：

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

时间复杂度O(n)

空间复杂度O(1)

70. 爬楼梯

文档讲解：代码随想录

视频讲解：

状态：去年7月11日做过，一周年了，结果还是不会做。想dp数组的定义，想了好久，不确定到底该怎么定义，到底是第i走了几个台阶 or 一共走了多少台阶 or 剩下多少台阶，但最后需要返回的是方法数量，这该咋办呢？

我的错误思路：

        # dp[i]是走完第i个台阶后，一共走了多少台阶# 递推公式 dp[i] = dp[i-1] + 1或2dp = [0] * n # 每次都走一个台阶，最多n步dp[0] = 1  # 但也有可能是2?if dp[-1] < n:  # 该确定遍历顺序了，怎么遍历?dp

正确思路是直接考虑每层楼梯的方法数目：

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯和到第一层楼梯状态推导出来。

动规五部曲：

1. 一维数组 dp[i]：爬到第i层楼梯，有dp[i]种方法

2. 递推公式：考虑最后一步走几个台阶，有两种情况1或者2。上i-1层楼梯，有dp[i - 1]种方法，那么再跳一个台阶就是dp[i]；上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶就是dp[i]。所以爬到第i层楼梯，有dp[i] = dp[i - 1] + dp[i - 2] 种方法。

3. 初始化：从dp数组定义的角度出发，不用考虑dp[0]的初始化，直接dp[1] = 1，dp[2] = 2，然后从i = 3开始递推

4. 从前向后遍历

5. 举例推导dp数组 1 2 3 5 8 13

斐波那契数列：0、1、1、2、3、5、8、13、21、34……

与斐波那契数列后半截一样的

class Solution:def climbStairs(self, n: int) -> int:if n == 1:return ndp = [0]*(n+1) # 因为python下标从0开始，到n 长度为n+1dp[1] = 1dp[2] = 2for i in range(3,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

注意！一定要注意边界条件的处理！如果不写 if n==1: return n 的话，当n = 1时，dp[2] = 2 处就会报错list out of range。

空间和时间复杂度：O(n) 此题也可以像上一题一样优化空间复杂度为O(1)

拓展：这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。这其实是一个完全背包问题，后面会讲。

746. 使用最小花费爬楼梯

文档讲解：代码随想录

视频讲解：

状态：自己做对了！类比上一题。

动规五部曲：

定义：dp[i]是到达第i个台阶需要支付的最少费用

公式：dp[i] = min((dp[i-1] + cost[i-1]), dp[i-2] + cost[i-2])

初始化：dp[0] = 0 dp[1] = 0 题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于跳到下标 0 或者下标 1 是不花费体力的

顺序：从前向后

举例：

cost = [1,100,1,1,1,100,1,1,100,1]

下标 0 1 2 3 4 5 6 7 8 9 楼顶

dp数组 0 0 1 2 2 3 3 4 4 5 6 确定dp数组长度为len(cost)+1

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0]*(len(cost)+1)dp[0] = 0dp[1] = 0for i in range(2,len(cost)+1): # 从2开始推导dp[i] = min((dp[i-1] + cost[i-1]), dp[i-2] + cost[i-2])return dp[-1]