【Day 54 】2024-05-31 - 746.使用最小花费爬楼梯

[azl397985856]

746.使用最小花费爬楼梯

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

前置知识

• 动态规划

  题目描述

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

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

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

 

示例 1：

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

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

提示：

cost 的长度范围是 [2, 1000]。 cost[i] 将会是一个整型数据，范围为 [0, 999] 。

[hillsonziqiu]

解法描述

一通遍历，让每次比较走一步或者走两步相加结果的最小值求出来，然后累加即可

代码

/*
 * @lc app=leetcode.cn id=746 lang=javascript
 *
 * [746] 使用最小花费爬楼梯
 */

// @lc code=start
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  let [prev, curr] = [0, 0];
  for (let i = 2; i <= cost.length; i++) {
    const next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
    prev = curr;
    curr = next;
  }

  return curr;
};
// @lc code=end

复杂度分析

• 时间复杂度：O(n);
• 空间复杂度：O(1);

[lxy1108]

思路

动态规划

python3代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0]*(len(cost)+1)
        for i in range(2,len(cost)+1):
            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
        return dp[-1]

复杂度分析

空间复杂度 时间复杂度均为o(n)

[Martina001]

class Solution { public int minCostClimbingStairs(int[] cost) { / int n = cost.length; int memo[] = new int[n]; Arrays.fill(memo,-1); memo[0] = cost[0]; memo[1] = cost[1]; dfs(cost,n-1,memo); return Math.min(memo[n-1],memo[n-2]);/ return dp1(cost); }

private int dfs(int[] cost,int i,int []memo){
    if(memo[i] != -1) return memo[i];
    if(i == 0){
        return memo[i];
    }
    if(i == 1){
        return memo[i];
    }
    memo[i] = Math.min(dfs(cost,i-1,memo),dfs(cost,i-2,memo))+cost[i];
    return memo[i];
}

/**
 * 再来根据dfs写一下动规
 * @param cost
 * @return
 */
private int dp1(int []cost){
    int n = cost.length;
    int dp[] = new int[n];
    dp[0] = cost[0];
    dp[1] = cost[1];
    for(int i = 2;i<n;i++){
        dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i];
    }
    return Math.min(dp[n-1],dp[n-2]);
}

}

[zhiyuanpeng]

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0] * (len(cost)+1) dp[0], dp[1] = cost[0], cost[1] for i in range(2, len(cost)+1): dp[i] = min(dp[i-1], dp[i-2]) + (cost[i] if i != len(cost) else 0) return dp[-1]

[Dtjk]

class Solution: def minCostClimbingStairs(self, cost: list[int]): cost = cost + [0] dp = [0]*len(cost) dp[0], dp[1] = cost[0], cost[1] for i in range(2, len(cost)): dp[i] = min(dp[i-1], dp[i-2]) + (cost[i]) return dp[-1]