题目来源
本题来源为：
题目描述
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
题目解析
通过题目给的两个实例来分析一下题目：
注意：楼顶是在整个数组外面而不是数组的最后一个位置。
每次爬楼梯只能爬一层或者两层。
算法原理
解法一：
1.状态表示
经验+题目要求：
以i位置为结尾…
对于本题而言就是：
dp[i]表示：以i位置为结尾时，最小花费
2.状态转移方程
在推方程之前，我们先画一下可能遇到的情况：
通过画图，我们知道到达i位置会有两种情况。
我们根据最近的一步来划分问题：
因此，本题的状态转移方程为：
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
3.初始化
本题会出现越界的情况为0位置和1位置：
因此本题初始化为：
dp[0]=dp[1]=0;
4.填表顺序
根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2位置的值，因此我们的填表顺序为：从左往右
5.返回值
dp[n]
代码实现
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { // 1.创建dp表 // 2.初始化 // 3.填表 // 4.返回值 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.状态表示
经验+题目要求：
以i位置为结尾…
对于本题而言就是：
dp[i]表示：以i位置为开始时，到达楼顶时的最小花费
2.状态转移方程
在推方程之前，我们先画一下可能遇到的情况：
通过画图，我们知道到达i位置会有两种情况。
我们根据最近的一步来划分问题：
因此，本题的状态转移方程为：
dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i])
3.初始化
因为最终要到达n位置，因此要初始化n-1与n-2的位置：
因此初始化为：
dp[n-1]=cost[n-1]; dp[n-2]=cost[n-2];
4.填表顺序
根据状态转移方程，我们计算dp[i]位置的值需要i+1与i+2位置的值，因此我们的填表顺序为：从右往左
5.返回值
返回dp[0]与dp[1]的最小值
代码实现
class Solution { public: //方法二： int minCostClimbingStairs(vector<int>& cost) { // 1.创建dp表 // 2.初始化 // 3.填表 // 4.返回值 int n=cost.size(); vector<int> dp(n); dp[n-1]=cost[n-1]; dp[n-2]=cost[n-2]; for(int i=n-3;i>=0;i--) { dp[i]=min(dp[i+1]+cost[i],dp[i+2]+cost[i]); } return min(dp[0],dp[1]); } };
时间复杂度：O(N)
空间复杂度：O(N)
![[最全算法总结]我是如何将递归算法的复杂度优化到O(1)的](https://ucc.alicdn.com/pic/developer-ecology/djggblw76kgva_b042975a18ee4c269c783f8d41cf957f.png?x-oss-process=image/format,webp/resize,h_160,m_lfit)