使用最小花销爬楼梯

746. 使用最小花费爬楼梯

给你一个整数数组 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[i]表示在i台阶跳跃需要花费的体力值，花费体力值后你可以选择跳1个或2个阶梯，你可以选择在下标为0或下标为1的台阶开始跳

确定dp数组及下标的含义

dp[i]表示到达第i个台阶跳跃所需要的最少体力值

到达顶层可以从dp[i-2]和dp[i-1]选择较小者

确定递推公式

dp[i]可以由两个途径达到，dp[i-1]和dp[i-2]，那么要选择哪个呢？

题目要求花费的体力最少，故选择较小者

dp[i] = Math.min( dp[i-2], dp[i-1]) + cost[i];

初始化dp数组

dp[0] = cost[0];
dp[1] = cost[1];

确定遍历顺序

由递推公式，第i个数由第i-2和第i-1个数推出，遍历顺序一定由前往后遍历

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        //dp[i]表示在下标为i台阶跳跃需要最小的花费
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2 ;  i < n ; i++){
            dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i]; 
        }
        return Math.min(dp[n-1],dp[n-2]);
    }
}

-
时间复杂度：$O(n)$

• 空间复杂度：$O(n)$