【LeetCode每日一题】——746.使用最小花费爬楼梯

一【题目类别】

• 数组

二【题目难度】

• 简单

三【题目编号】

• 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

七【解题思路】

• 该题为标准的动态规划题目
• 对于第i个位置，cost[i]为第i个位置向上爬的花费，dp[i]为到达第i个位置所需要的最小的花费，所以可以得到动态转移方程：
  • dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2])
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时空频度】

• 时间复杂度：$O(n)$，$n$为传入的数组的长度
• 空间复杂度：$O(n)$，$n$为传入的数组的长度

九【代码实现】

1. Java语言版

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        // 动态规划数组
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        // 计算爬楼梯的最小花费：到达第 i 层的最小花费由前一层或前两层的最小花费加上当前层的花费决定
        for (int i = 2; i < (n + 1); i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        // 返回结果
        return dp[n];
    }
}

2. Python语言版

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 动态规划数组
        dp = [0] * (n + 1)
        # 计算爬楼梯的最小花费：到达第 i 层的最小花费由前一层或前两层的最小花费加上当前层的花费决定
        for i in range(2, (n + 1)):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        # 返回结果
        return dp[n]

3. C语言版

int minCostClimbingStairs(int* cost, int costSize)
{
    // 动态规划数组
    int* dp = (int *)calloc((costSize + 1), sizeof(int));
    // 计算爬楼梯的最小花费：到达第 i 层的最小花费由前一层或前两层的最小花费加上当前层的花费决定
    for (int i = 2; i <= costSize; i++)
    {
        dp[i] = fmin(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
    }
    int res = dp[costSize];
    free(dp);
    // 返回结果
    return res;
}

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C语言版
   

原文地址：https://blog.csdn.net/IronmanJay/article/details/143933978

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！