【教3妹学编程-算法题】使用最小花费爬楼梯

插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。
坚持不懈，越努力越幸运，大家一起学习鸭~~~

3妹：2哥2哥，你有没有看到新闻， 有人中了2.2亿彩票大奖！
2哥 : 看到了，2.2亿啊， 一生一世也花不完。
3妹：为啥我就中不了呢，不开心呀不开心。
2哥 : 得了吧，你又不买彩票，还是脚踏实地的好~
3妹：小富靠勤，中富靠德，大富靠命， 可能是我命不好。
2哥 : 你哪个是命不好， 你就是想不劳而获，想用最小的体力消耗来暴富吧。
3妹：说到最小体力消耗， 我今天看到一个关相关的题目，让我也来考考你吧~

题目：

给你一个整数数组 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 <= 1000
0 <= cost[i] <= 999

思路：

动态规划，
假设数组cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n?1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。

创建长度为 n+1的数组 dp，其中 dp[i] 表示达到下标 i 的最小花费。

由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0]=dp[1]=0。

当 2≤i≤n时，可以从下标 i?1 使用 cost[i?1]的花费达到下标 iii，或者从下标 i?2 使用 cost[i?2] 的花费达到下标 i。为了使总花费最小，dp[i]应取上述两项的最小值，因此状态转移方程如下：

dp[i]=min?(dp[i?1]+cost[i?1],dp[i?2]+cost[i?2])
依次计算 dp 中的每一项的值，最终得到的 dp[n] 即为达到楼层顶部的最小花费。

java代码：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}