问题描述

假设你面前有一段楼梯，楼梯上有许多台阶。每个台阶都有一个价格标签，表示你需要支付多少钱才能踏上这个台阶。你可以从第一个台阶开始，也可以从第二个台阶开始。每走一步，你可以选择上一个台阶或者上两个台阶。我们的目标是找到一条路，让你到达楼梯顶部所花费的钱最少。

示例

例如，楼梯的价格如下：

0     1     2     3     4
[10, 15, 20, 5, 10]

如果我们从第一个台阶开始，那么我们会支付 10 元，然后可以选择：

  • 再支付 15 元上一个台阶；
  • 或者支付 20 元上两个台阶。

显然，选择上两个台阶更划算。继续这个逻辑，我们会发现最便宜的到达顶部的路径是：

  1. 从第一个台阶开始，支付 10 元；
  2. 上两个台阶，支付 20 元；
  3. 再上两个台阶，支付 5 元；
  4. 最后上一个台阶，支付 10 元；

总共支付 10 + 20 + 5 + 10 = 45 元。

解决方案

为了找到最便宜的路径，我们可以从最后一个台阶开始向前推算。我们想知道，到达最后一个台阶之前，我们在哪里可以花最少的钱走到这里。

代码解释

我们来编写一个名为 minCostClimbingStairs 的方法，它接收一个整数数组 cost，表示每个台阶的价格。以下是这个方法的简单实现：

public class MinCostClimbingStairs {
    public int minCostClimbingStairs(int[] cost) {
        // 检查是否为空或只有一个元素
        if (cost == null || cost.length <= 1) {
            return 0;
        }

        // 初始化前两个台阶的花费
        int first = cost[0];
        int second = cost[1];

        // 如果数组长度为2，则返回两者中较小的一个
        if (cost.length == 2) {
            return Math.min(first, second);
        }

        // 从第三个台阶开始，计算最小花费
        for (int i = 2; i < cost.length; i++) {
            // 当前台阶的最小花费等于前两步中的最小花费加上当前台阶的价格
            int current = Math.min(first, second) + cost[i];
            // 更新前两步的花费
            first = second;
            second = current;
        }

        // 最后一步比较从第一个台阶开始和从第二个台阶开始的最小花费
        return Math.min(first, second);
    }

}

在这段代码中：

  • 我们首先检查输入是否有效。
  • 然后初始化前两个台阶的花费。
  • 接着，从第三个台阶开始，计算到达当前台阶的最小花费。
  • 每次都保留前两个台阶的花费，以便计算下一个台阶的最小花费。
  • 最后，返回从第一个台阶或第二个台阶开始到达顶部的最小花费。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。