【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语言版