继续上一道题目，在上一道题目的基础之上，我们来解决这一道爬楼梯最小费用题。
一.题目描述
二.思路(动态规划五部曲)
- 确定dp数组以及下标的含义
使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
对于dp数组的定义，大家一定要清晰！
2.确定递推公式
可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？
一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3.dp数组如何初始化
看一下递归公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。
那么 dp[0] 应该是多少呢？ 根据dp数组的定义，到达第0台阶所花费的最小体力为dp[0]，那么有同学可能想，那dp[0] 应该是 cost[0]，例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话，dp[0] 就是 cost[0] 应该是1。
4.确定遍历顺序
最后一步，递归公式有了，初始化有了，如何遍历呢？
因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
5.举例推导dp数组
拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：
如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。
以上分析完毕，整体C++代码如下：
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { vector<int> dp(cost.size() + 1); dp[0] = 0; // 默认第一步都是不花费体力的 dp[1] = 0; for (int i = 2; i <= cost.size(); i++) { dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[cost.size()]; } };
- 时间复杂度：O(n)
- 空间复杂度：O(n)
大家可以发现这道题目相对于上一道题目又难了一点，但整体思路是一样的。
大家加油！
