题目
提示
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
思路
题目分析
此题他说给一个数组，这个数组里面的值是代表每级台阶向上爬的费用，每次在相应台阶支付费用，可以选择爬一层台阶或者两层台阶，题目要求计算到达楼梯顶部所花的费用，既然要计算到达楼梯顶部所花费的费用，首先我们得知道楼梯顶部在哪？根据给定cost数组：题目中说cost[i]代表第i级台阶向上爬所需要的费用，因为楼梯顶部是不需要往上爬的，所以也没有支付费用 ，，根据所给的示例，对于示例1，cost有三位数，从第四项开始就没有支付费用，所以第四项也就是下标为三数，是楼梯顶部，类比示例2，cost有九级台阶，所以第十项就是楼梯顶部
另外，题目中说我们可以选择从0级台阶爬，也可以从1级台阶开始爬，这个也是根据最省钱的方案选择（如果从0级台阶爬，最省钱就选从0级台阶开始，如果从1级台阶爬最省钱就从1级台阶开始爬）.
动态规划原理
解法一：
1.状态表示biao
dp表里面的值表示的含义就是一个状态表示。
本题就是，dp[i]表示，到达第i个台阶的最小花费
2.状态转移方程
状态转移方程就是：dp[i]等于什么？一般情况下就是使用dp[i]前的状态或者(dp[i-1],dp[i-2]...)dp[i]后面的状态(dp[i+1],dp[i+2]...)推导出转移状态方程.那么怎么到达dp[i]呢，根据题目描述，支付后选择向上爬一个台阶，或者爬两个台阶，
a) 爬一个台阶,先到达i-1位置，支付cost[i-1]，向上爬一个台阶
b) 爬两个台阶，先到达i-2位置，支付cost[i-2]，向上爬两个台阶
cost[i-1]和cost[i-2]是一个定值，因此，到达i要花费最小，就是要到达i-1最小，到达i-2最小
根据上面状态表示的定义“dp[i]表示，到达第i个台阶的最小花费”所以到达i-1最小花费dp[i-1],到达dp[i-2]最小花费就是dp[i-2]，
根据以上分析，状态转移方程
dp[i]=dp[i-1]+cost[i-1]
dp[i]=dp[i-2]+cost[i-2]
最后将两种情况对比，之后取最小值。
3.初始化
初始化就是：保证填表的时候不越界，对该初始化的值要进行初始化
因为可以直接从第0级台阶和第1台阶开始不需要花钱，所以dp[0]=dp[1]=0
4.填表顺序
确定填表顺序是为了填写当前状态时，所需要的状态已经计算过了
因为算dp[i]时，所以只能先算前面（dp[i-1],dp[i-2])的，填表顺序就是从左往右
5.返回值
根据题目要求(到达i时所需要的最小花费）和状态表示返回我们要的答案
本题就是dp[n]
解法二：
1.状态表示
还是创建一个dp表
于解法一不同的是，这次的dp[i]表示，i位置到达楼顶的最小花费
2.状态转移方程
分析到达楼顶的最小花费的形成过程，因为dp[i]表示i位置到达楼顶的最小花费，说明此时已经 到达了第i级台阶，支付cost[i]后
a)走一步到达第i+1级台阶，再从i+1的位置走到顶部，
b)走两步到达第i+2级台阶，再从i+2的位置走到顶部
要到达顶部的花费最小，就需要让i+1到顶部最小，根据状态表示，就可以把i+1到顶部最小表示为dp[i+1]，同理i+2到顶部最小表示为dp[i+2]
所以状态转移方程可以表示为
dp[i]=cost[i]+dp[i+1]
dp[i]=cost[i]+dp[i+2]
然后就是两种情况比较，取最小值
3.初始化
因为要用到后两个位置，所以要初始化倒数第一个台阶到顶部的最小花费，和倒数第二个台阶到顶部的最小花费，dp[n-1]=cost[n-1],dp[n-2]=cost[n-2]
4.填表顺序
观察状态转移方程看出，由后面的值得出前面的值，所以填表顺序就是 从后往前
5.返回值
我们的状态表示，dp[i]表示第i台阶到顶部的最小花费，根据题目要求的是-到达i时所需要的最小花费，也就是开始到顶部的最小花费，开始我们可以从 0开始，也可以从1开始，所以返回dp[0]和dp[1]两者的较小值。
代码
还是原来的四步
1.创建dp表
2.初始化
3.填表顺序
4.返回答案
解法一：
int minCostClimbingStairs(int* cost, int costSize) { //创建dp表 int dp[10000]={0}; //初始化 dp[0]=dp[1]; //填表 for(int i=2;i<=costSize;i++) { dp[i]=(dp[i-1]+cost[i-1]<dp[i-2]+cost[i-2])?dp[i-1]+cost[i-1]:dp[i-2]+cost[i-2]; } //返回 return dp[costSize]; }
空间复杂度：O(n）
时间复杂度：O(n)
解法二：
int minCostClimbingStairs(int* cost, int costSize) { //创建dp表 int dp[10000]={0}; //初始化 dp[costSize-1]=cost[costSize-1]; dp[costSize-2]=cost[costSize-2]; //填表 for(int i=costSize-3;i>=0;i--) { dp[i]=(dp[i+1]+cost[i]<dp[i+2]+cost[i])?dp[i+1]+cost[i]:dp[i+2]+cost[i]; } //返回 return (dp[0]>dp[1])?dp[1]:dp[0]; }
空间复杂度：O(n）
时间复杂度：O(n)
