一、动态规划（DP）理论基础
1.常见的5种问题：动规基础题、背包问题、打家劫舍、股票问题、子序列问题
2.动规五部曲：
（1）确定动规数组，了解其下标含义
（2）确定递推公式
（3）dp数组的初始化方法
（4）确定遍历顺序
（5）推导dp数组，打印dp数组
二、斐波那契数列
（1）dp数组：记录第i个斐波那契数
（2）dp[i]=dp[i-1]+dp[i-2]
（3）dp[0]=0,dp[1]=1
（4）后一个数由前两个数决定，因此从前往后遍历
（5）返回最后一个元素
class Solution {
public:int fib(int n) {if(n<=1)return n;vector<int>dp(n+1);dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};三、爬楼梯
（1）dp数组：第i阶能到达的方法
（2）dp[i]=dp[i-2]+dp[i-1]，因为到第n阶可以看做是第n-1阶花一步到第n阶，也可以看做是第n-2阶花两步到第n阶，也就是说，到第n-1阶和到第n-2阶共有多少种方法，到第n阶就有多少种方法，第n-2阶也可以先花一步到第n-1阶，但是不需要计算这部分，因为在计算n-1的方法时已经算过了。
（3）初始化：dp[1]=1,dp[2]=2
（4）同上，一阶一阶的爬楼梯，从前往后遍历
（5）返回最后一个元素
class Solution {
public:int climbStairs(int n) {if(n<=1)return n;vector<int>dp(n+1);dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-2]+dp[i-1];}return dp[n];}
};
四、最小花费爬楼梯
（1）dp数组含义：到第i阶需要的最小花费
（2）递推公式：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])意思是，可以从i-1阶到顶部，也可以从i-2阶到顶部，取其中花费最小的一步
（3）初始化：dp[0]=0,dp[1]=0（可以直接从0，1开始，开始不花费体力）
（4）同上，爬楼梯从前往后遍历
（5）返回顶端元素dp[n]（n=cost.size()）
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();vector<int>dp(n+1);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];}
};
