Day38 | 509. 斐波那契数, 70. 爬楼梯, 746. 使用最小花费爬楼梯
理论基础
重点在于方法论的使用上面：
1、确定dp数组（dp table）以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组
斐波那契数
LeetCode题目：https://leetcode.cn/problems/fibonacci-number/
整体思路
按照五步进行分析，dp数组在本题目中的含义应该是数值i所具有的斐波那契数列。递推公式由斐波那契数的特性可得，dp[i] = dp[i-1] + dp[i-2]。对于斐波那契数，dp[1]和dp[0]的值是可以直接得到的，所以初始化前两个数值。
最后，根据递推公式可以执行正序的遍历。
class Solution {
public:int fib(int n) {if(n<=1) return n;vector<int> dp(2);dp[0] = 0;dp[1] = 1;int sum = 0;for(int i=2;i<=n;i++){sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return sum;}
};
爬楼梯
LeetCode题目：https://leetcode.cn/problems/min-cost-climbing-stairs/
解题思路
该题主要是对爬楼梯进行抽象。dp数组应当是对应到达第i个台阶所需要的方法。同时，由于可以爬一步或者两步，所以递推公式中能得到的到达第i个台阶由两个式子共同决定，即dp[i-1] + dp[i-2]。其中dp[i-1]其实可以理解为dp[i-2]使用两个一步的方法。
确定遍历方法，由于每个dp的条件应该由之前的条件确定，因此需要进行正序遍历。此外，为了保证i对应第i个台阶，所以应该dp初始化n+1个数值。
代码如下：
class Solution {
public:int climbStairs(int n) {if(n==1) return 1;vector<int> dp(n+1,0);dp[1] = 1;dp[2] = 2;for (int i = 3;i <= n;i++) {dp[i] += dp[i-2] + dp[i-1];}return dp[n];}
};
使用最小花费爬楼梯
LeetCode题目：https://leetcode.cn/problems/climbing-stairs/
解题思路
该题主要是对爬楼梯进行抽象。dp数组应当是对应到达第i个台阶所需要的花费。同时，由于可以爬一步或者两步，所以递推公式中能得到的到达第i个台阶由两种花费的情况，即dp[i-1] + cost[i-1]和dp[i-2] + cost[i-2]。取得两者中的最小值即可。
确定遍历方法，由于每个dp的条件应该由之前的条件确定，因此需要进行正序遍历。此外，为了保证i对应第i个台阶，所以应该dp初始化n+1个数值。
代码如下：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();/* dp数组的含义：到达第i个台阶的最小花费 *//* 在第i个台阶向上到下一层时才花销第i个cost */vector<int> dp(n+1,0);dp[0] = 0;dp[1] = 0;for (int i = 2;i <= n;i++) {dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);}return dp[n];}
};
