动态规划(算法)---03.斐波那契数列模型_最小花费爬楼梯
题目链接：
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
https://leetcode.cn/problems/min-cost-climbing-stairs/description/
一、题目解析
题目：
解析：
题目说cost[i]为从某一个台阶向上爬的的费用，我们只要支付这个费用，就可以选择向上爬一或两个台阶，求爬到顶部的最小费用
这里有一个易错点：容易把最后支付费用的台阶当成楼顶，我们通过示例1知道，一共有三个台阶，我们在第二个台阶向上爬仍然需要两步，所以说最后一个台阶的后面才是楼顶！
我们从第一个台阶或者第二个台阶出发，每次都选择最小花费直达终点得到的最小花费才是我们想要的答案
二、算法原理
1、状态表示
我们在状态标识的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。
状态简单理解就是dp表内某一个值代表的含义。
如何确定状态表示
- 题目要求
简单的题目里一般会给出
- 经验+题目要求
越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。
- 分析问题的过程中，发现重复子问题
分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。
那我们这道题的状态表示应该是是什么样的，是以一个位置为结尾开始算起呢，还是以一个位置为开始？
这道题两种状态都可以，我们都给大家讲解一下：
以一个位置为结尾：dp[i]表示：到达i位置时的最小花费
以一个位置为结尾：dp[i]表示：从i位置开始，到达楼顶，此时的最小花费
2、状态转移方程
确定状态表示之后我们就可以根据状态标识推出状态转移方程
状态转移方程是什么？
不讲什么复杂的，简单来说状态转移方程就是 dp[i]等于什么 dp[i]=？
这个就是状态转移方程，我们要做的，就是推出dp[i]等于什么
我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步
我们在这道题先简单了解下什么是状态转移方程，之后比较难的题目再细推
在这道题中，我们应该用之前或者之后的状态，推导出dp[i]的值
以一个位置为结尾：
根据最近的一步，来划分问题：
我们知道，dp[i]表示，到达i位置时的最小花费，但在i位置之前，又有两种状态：
- 从i-1位置花费cost[i-1]走一步到达i
- 从i-2位置花费cost[i-2]走两步到达i
我们要从两种状态中选出到达i位置的最小花费，那么我们就需要选出到达i-1和i-2位置的最小花费
i-1和i-2位置的最小花费是：dp[i-1]和dp[i-2]
从中选出i位置的最小花费，那么我就就需要比较 dp[i-1]+cost[i-1]与dp[i-2]+cost[i-2]的大小！
那么我们的状态转移方程就确定：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
以一个位置为开始：
我们知道，dp[i]表示从i位置开始，到达楼顶，此时的最小花费。但在i位置之后，又有两个状态：
- 在i位置支付cost[i]往后走一步到i+1的位置
- 在i位置支付cost[i]往后走两部到i+2的位置
我们要从两种状态中选出此时i位置的最小花费，那么我们就需要选出i-1和i-2位置此时的最小花费
cost[i]是一定的，我们只需要选出i+1或者i+2位置到达楼顶的花费最小就行了
即是dp[i+1]和dp[i+2]
从中选出i位置的最小花费，那么我就需要比较 dp[i-1]+cost[i-1]与dp[i-2]+cost[i-2]的大小！
那么我们的状态转移方程就确定：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3、初始化
我们创建dp表就是为了把他填满，我们初始化是为了防止在填表的过程中越界
怎么谈越界？
如果我们从第一个台阶或者第二个台阶开始填，那dp[i-1]与dp[i-2]会越界！
以一个位置为结尾：
我们需要给dp表初始化为0，由cost数组中的花费来填写dp表
如果我们从最后一个台阶或者倒数第二个台阶开始填，那dp[i+1]和do[i+2]会越界
以一个位置为开始：
我们需要给dp表最后两个数进行初始化，即是最后一个台阶或者倒数第二个台阶到达楼顶的最小花费
4、填表顺序
以一个位置为结尾：
我们需要先知道dp[i-1]与dp[i-2]的值，才能得到dp[i]的最小花费，所以我们需要从左到右挨个填写！
以一个位置为开始：
我们需要先知道dp[i+1]与dp[i+2]的值，才能得到dp[i]的最小花费，所以我们需要从右到左挨个填写！
5、返回值
以一个位置为结尾：
返回dp[i]即可，此时i表示为楼顶
以一个位置为开始：
因为我们所求的是从i位置开始网上爬，此时i位置的最小花费，我们最开始是在第一个台阶或者第二个台阶中选择一个向上怕的，所以当我们填表顺序完成之后，我们需要在dp[0]与dp[1]中再选择一个最小花费，即：min(dp[0],dp[1])
三、编写代码
以一个位置为结尾：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();
//1、创建dp表，大小设置为n+1，是因为楼顶在最后一个台阶之后！vector<int> dp(n+1);
//2、这里初始化省去了，因为我们只需要将dp表内元素置零，在创建dp表时就可以做到
//3、填表顺序，从第三个台阶开始填，否则会越界for(int i=2;i<n+1;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}
//4、返回值为楼顶,第n+1个元素return dp[n];}
};以一个位置为开始：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();//1、创建dp表，这里的大小为n，是因为我们不用从楼顶再往上爬vector<int> dp(n);//2、初始化dp[n-1]=cost[n-1];dp[n-2]=cost[n-2];//3、填表顺序，从右到左for(int i=n-3;i>=0;i--){dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]);}//4、返回值return min(dp[0],dp[1]);}