509. 斐波那契数
题目简述：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定n，计算F(n)
思路：
1. 递归肯定不行，计算量太大
2. 直接dp
代码如下：
class Solution: def fib(self, n: int) -> int: fib=[] fib.append(0) fib.append(1) if n==0: return 0 if n==1: return 1 for i in range(2,n+1): fib.append(fib[i-2]+fib[i-1]) return fib[n]
70. 爬楼梯
题目简述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路
1. 爬到第k阶的方法数=爬到第k-1阶方法数*1+爬到第k-2阶*1。要到达k，必须先到达k-1或者k-2
2. 这是因为在k-1阶，只有一种选择即一次上一阶的方法到达第k阶；在k-2阶，有1种选择，即一下走两个台阶，1+1的情况必须先到k-1，这和一开始在k-1重复了
3. 而在k-3阶还是必须先到达k-2或者k-1，因为一次最多走两阶，k-3情况已经被k-2和k-1包含进去了
4. 于是用动态规划，本质上还是斐波那契数列
代码如下：
class Solution: def climbStairs(self, n: int) -> int: if n==1: return 1 if n==2: return 2 dp=[1,1] for i in range(2,n+1): dp.append(dp[i-1]+dp[i-2]) return dp[n]
746. 使用最小化花费爬楼梯
题目简述：
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
思路：
1. 第1个楼梯，下标为0，可直接到达，dp[0]=0
2. 第2个楼梯，下标为1，可直接到达，dp[1]=0
3. 第3个楼梯，下标为2，可以从第1个楼梯跳上来，也可以从第2个楼梯跳上来，取最小值dp[2]=min(dp[0]+cost[0],dp[1]+cost[1])
4. 第k个楼梯，下标为k-1，有dp[k-1]=min(dp[k-2]+cost[k-2],dp[k-1]+cost[k-1])
5. 爬完楼梯，即求dp[n]
5. 于是利用动态规划
代码如下：
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp=[0,0] n=len(cost) for j in range(2,n+1): dp.append(min(dp[j-2]+cost[j-2],dp[j-1]+cost[j-1])) return dp[n]