动态规划攻略之：用最小花费爬楼梯

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

题目

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例1：

1
2
3
ini复制代码输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

示例2：

1
2
3
ini复制代码输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

解题思路

根据题目要求，我们可以利用动态规划的思路来解题。

首先，到达第 i 级台阶的阶梯顶部的最小花费，有俩个选择：

  • 先付出最小总花 minCost[i-1] 到达第i级台阶（第i-1级台阶的阶梯顶部），踏上第i级台阶需要再花费 cost[i]，再迈一步到达第i级台阶的阶梯顶部，最小总花费为minCost[i-1] + cost[i])；
  • 先付出最小总花费 minCost[i-2] 到达第i-1级台阶（第i-2级台阶的阶梯顶部），踏上第i-1级台阶需要再花费 cost[i-1]，再迈两步跨过第i级台阶直接到达第i级台阶的阶梯顶部，最小总花费为minCost[i-2] + cost[i-1])；

则minCost[i]是上面这两个最小总花费中的最小值。

因此状态转移方程如下：

minCost[i] = min(minCost[i-1] + cost[i], minCost[i-2] + cost[i-1])。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int size = cost.length;
        int[] minCost = new int[size];
        minCost[0] = 0;
        minCost[1] = Math.min(cost[0], cost[1]);
        for (int i = 2; i < size; i++) {
            minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);
        }
        return minCost[size - 1];
    }
}

最后

时间复杂度为：O(N)

空间复杂度为：O(N)

往期文章：

请你喝杯 ☕️ 点赞 + 关注哦～

  1. 阅读完记得给我点个赞哦，有👍 有动力
  2. 关注公众号— HelloWorld杰少，第一时间推送新姿势

最后，创作不易，如果对大家有所帮助，希望大家点赞支持，有什么问题也可以在评论区里讨论😄～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%