1. 题目链接：746. 使用最小花费爬楼梯
2. 题目描述
根据一般的思维，我们会认为本题中数组的最后一个位置是楼顶，但是根据第一个例子，如果最后一个位置是楼顶，花费最少应该为10，但是结果是15，因此本体中的楼顶指的是数组外的下一个位置。
动态规划算法对于一维数组来说，我们的思路是创建动态表dp，定义dp[i]的含义，然后根据含义去利用dp表之前或者之后的值去表示dp[i],对于本道题，两种思路，都可行，因此，本体两种方法都介绍一下。
3. 解法（动态规划）
解法一：
1. 状态表示：
我们根据题目要求，我们设dp[i]以i为结尾，跳到i台阶的最小花费
2. 状态转移方程：
我们现在要尝试根据dp[i]位置之前或之后的值去表示出dp[i]。
因为一次可以跳一阶或者两阶，所以跳到第i阶之前最近的状态，要么跳到i - 1,然后再支付cost[i - 1]，向上跳到i;要么跳到i - 2,再支付cost[i - 2],跳到i。
那么基于上述两种情况，dp[i]就有两种取值，因为求最小，我们取两个之中最小的值。
那么 状态表示方程就是dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])
3. 初始化：
我们初始化要保证不能出现越界的情况，对于上述方程，我们发现dp[0]、dp[1]，取前两个值会越界，因此，我们根据题意初始化这两个值。
4. 填表顺序：
根据状态表示方程，我们要先知道dp[i - 1]、dp[i - 2],才能知道dp[i],填dp表顺序是从左往右。
5. 返回值：
返回到达楼顶的最小花费，即dp[n].
算法代码：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp( n + 1);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];}
};解法二：
1. 状态表示：
我们设dp[i]的含义为从i出发，到达楼顶的最小花费。
2. 状态转移方程：
那么此时的最近状态是，从i出发支付第i阶的费用，然后向后跳一阶到达i + 1,或者向后跳两阶到达i + 2。
那么求从i出发到楼顶的最小花费，就是当前i阶的花费加上从i + 1出发 的最小花费或从i + 2出发的最小花费，即状态表示方程是dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
3. 初始化：
当前状况下的边界情况，我们发现从n - 2往后跳两步或者从n - 1出发往后跳一步，就会到达楼顶，这时我们仅需要支付cost[n - 2]和cost[n - 1]的费用， 即dp[n - 2] = cost[n - 2]，dp[n - 1] = cost[n - 1]。
4. 填表顺序：
此时我们需要知道dp[i]位置值，我们需要先知道dp[i + 1]、dp[i + 2]，因此填表顺序是从右往左。
5. 返回值：
由题意知，我们可以从0阶或者1阶出发，因此为此时dp[0]表示从0出发到达楼顶的最小花费，dp[1]表示从1出发到达楼顶的最小花费，因此，我们取两者之间的最小值返回。
算法代码：
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n);dp[n - 2] = cost[n - 2];dp[n - 1] = cost[n - 1];for(int i = n - 3; i >= 0;i--){dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);}return min(dp[0],dp[1]);}
};