题目描述

题目链接：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

我的题解

方法一：动态规划

思路

当爬到第n阶楼梯时，有两种方法可以到达：

从n-1阶楼梯爬1阶到第n阶
从n-2阶楼梯爬2阶到第n阶

设dp[i]为爬到第i层的最小花费，则动态规划公式为：dp[i] = Math.min( dp[i-1] + dp[i-2] ) + cost[i]

因为当前状态只依赖前两个状态，因此，可以使用变量优化

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a = cost[0], b = cost[1], c;
        for (int i = 2; i < cost.length; i++) {
            c = Math.min(a, b) + cost[i];
            a = b;
            b = c;
        }
        return Math.min(a, b);
    }
}