Skip to content

Latest commit

 

History

History
544 lines (414 loc) · 17.3 KB

0746.使用最小花费爬楼梯.md

File metadata and controls

544 lines (414 loc) · 17.3 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!

746. 使用最小花费爬楼梯

力扣题目链接

旧题目描述

数组的每个下标作为一个阶梯,第 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] 。

算法公开课

《代码随想录》算法视频公开课::动态规划开更了!| LeetCode:746. 使用最小花费爬楼梯,相信结合视频再看本篇题解,更有助于大家对本题的理解


本题之前的题目描述是很模糊的,看不出来,第一步需要花费体力值,最后一步不用花费,还是说 第一步不花费体力值,最后一步花费。

后来力扣改了题目描述,新题目描述

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

思路

在力扣修改了题目描述下,我又重新修改了题解

修改之后的题意就比较明确了,题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的, 从 下标 0 下标1 开始跳就要花费体力了。

  1. 确定dp数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

对于dp数组的定义,大家一定要清晰!

  1. 确定递推公式

可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

  1. dp数组如何初始化

看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。

那么 dp[0] 应该是多少呢? 根据dp数组的定义,到达第0台阶所花费的最小体力为dp[0],那么有同学可能想,那dp[0] 应该是 cost[0],例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话,dp[0] 就是 cost[0] 应该是1。

这里就要说明本题力扣为什么改题意,而且修改题意之后 就清晰很多的原因了。

新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。

所以初始化 dp[0] = 0,dp[1] = 0;

  1. 确定遍历顺序

最后一步,递归公式有了,初始化有了,如何遍历呢?

本题的遍历顺序其实比较简单,简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

但是稍稍有点难度的动态规划,其遍历顺序并不容易确定下来。 例如:01背包,都知道两个for循环,一个for遍历物品嵌套一个for遍历背包容量,那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢? 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢?

这些都与遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的!

  1. 举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

如果大家代码写出来有问题,就把dp数组打印出来,看看和如上推导的是不是一样的。

以上分析完毕,整体C++代码如下:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);
        dp[0] = 0; // 默认第一步都是不花费体力的
        dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

还可以优化空间复杂度,因为dp[i]就是由前两位推出来的,那么也不用dp数组了,C++代码如下:

// 版本二
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
            dp0 = dp1; // 记录一下前两位
            dp1 = dpi;
        }
        return dp1;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

当然如果在面试中,能写出版本一就行,除非面试官额外要求 空间复杂度,那么再去思考版本二,因为版本二还是有点绕。版本一才是正常思路。

拓展

旧力扣描述,如果按照 第一步是花费的,最后一步不花费,那么代码是这么写的,提交也可以通过

// 版本一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0]; // 第一步有花费
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 注意最后一步可以理解为不用花费,所以取倒数第一步,第二步的最少值
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};

当然如果对 动态规划 理解不够深入的话,拓展内容就别看了,容易越看越懵。

总结

大家可以发现这道题目相对于 昨天的动态规划:爬楼梯又难了一点,但整体思路是一样的。

动态规划:斐波那契数动态规划:爬楼梯再到今天这道题目,录友们感受到循序渐进的梯度了嘛。

每个系列开始的时候,都有录友和我反馈说题目太简单了,赶紧上难度,但也有录友和我说有点难了,快跟不上了。

其实我选的题目都是有目的性的,就算是简单题,也是为了练习方法论,然后难度都是梯度上来的,一环扣一环。

但我也可以随便选来一道难题讲呗,这其实是最省事的,不用管什么题目顺序,看心情找一道就讲。

难的是把题目按梯度排好,循序渐进,再按照统一方法论把这些都串起来,所以大家不要催我哈,按照我的节奏一步一步来就行了。

其他语言版本

以下版本其他语言版本,大多是按照旧力扣题解来写的,欢迎大家在Github提交pr,修正一波。

Java

// 方式一:第一步不支付费用
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];

        // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0
        dp[0] = 0;
        dp[1] = 0;

        // 计算到达每一层台阶的最小费用
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[len];
    }
}
// 方式二:第一步支付费用
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        //最后一步,如果是由倒数第二步爬,则最后一步的体力花费可以不用算
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}
// 状态压缩,使用三个变量来代替数组
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。
        int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0;
        // 前两个台阶不需要费用就能上到,因此从下标2开始;因为最后一个台阶需要跨越,所以需要遍历到cost.length
        for (int i = 2; i <= cost.length; i ++) {
            // 此处遍历的是cost[i - 1],不会越界
            currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]);
            beforeTwoCost = beforeOneCost;
            beforeOneCost = currentCost;
        }
        return currentCost;
    }
}

Python

动态规划(版本一)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)
        dp[0] = 0  # 初始值,表示从起点开始不需要花费体力
        dp[1] = 0  # 初始值,表示经过第一步不需要花费体力
        
        for i in range(2, len(cost) + 1):
            # 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步
            # 选择其中花费体力较小的路径,加上当前步的花费,更新dp数组
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        
        return dp[len(cost)]  # 返回到达楼顶的最小花费

动态规划(版本二)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp0 = 0  # 初始值,表示从起点开始不需要花费体力
        dp1 = 0  # 初始值,表示经过第一步不需要花费体力
        
        for i in range(2, len(cost) + 1):
            # 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步
            # 选择其中花费体力较小的路径,加上当前步的花费,得到当前步的最小花费
            dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2])
            
            dp0 = dp1  # 更新dp0为前一步的值,即上一次循环中的dp1
            dp1 = dpi  # 更新dp1为当前步的最小花费
        
        return dp1  # 返回到达楼顶的最小花费

动态规划(版本三)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * len(cost)
        dp[0] = cost[0]  # 第一步有花费
        dp[1] = cost[1]
        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
        # 注意最后一步可以理解为不用花费,所以取倒数第一步,第二步的最少值
        return min(dp[-1], dp[-2])

动态规划(版本四)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        prev_1 = cost[0]  # 前一步的最小花费
        prev_2 = cost[1]  # 前两步的最小花费
        for i in range(2, n):
            current = min(prev_1, prev_2) + cost[i]  # 当前位置的最小花费
            prev_1, prev_2 = prev_2, current  # 更新前一步和前两步的最小花费
        return min(prev_1, prev_2)  # 最后一步可以理解为不用花费,取倒数第一步和第二步的最少值

Go

func minCostClimbingStairs(cost []int) int {
    f := make([]int, len(cost) + 1)
    f[0], f[1] = 0, 0
    for i := 2; i <= len(cost); i++ {
        f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2])
    }
    return f[len(cost)]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
第二种思路: dp[i]表示从i层起跳所需要支付的最小费用
递推公式:
i<n :dp[i] = min(dp[i-1],dp[i-2])+cost[i]
i==n:dp[i] = min(dp[i-1],dp[i-2]) (登顶)

func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	dp := make([]int, n+1)
	dp[0], dp[1] = cost[0], cost[1]
	for i := 2; i <= n; i++ {
		if i < n {
			dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
		} else {
			dp[i] = min(dp[i-1], dp[i-2])
		}
	}
	return dp[n]
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

JavaScript

var minCostClimbingStairs = function(cost) {
  const dp = [0, 0]
  for (let i = 2; i <= cost.length; ++i) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  }
  return dp[cost.length]
};

不使用 dp 数组

var minCostClimbingStairs = function(cost) {
  let dpBefore = 0,
    dpAfter = 0
    for(let i = 2;i <= cost.length;i++){
        let dpi = Math.min(dpBefore + cost[i - 2],dpAfter + cost[i - 1])
        dpBefore = dpAfter
        dpAfter = dpi
    }
    return dpAfter
};

TypeScript

function minCostClimbingStairs(cost: number[]): number {
  const dp = [0, 0]
  for (let i = 2; i <= cost.length; i++) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  }
  return dp[cost.length]
}

不使用 dp 数组

function minCostClimbingStairs(cost: number[]): number {
  let dpBefore = 0,
    dpAfter = 0
  for (let i = 2; i <= cost.length; i++) {
    let dpi = Math.min(dpBefore + cost[i - 2], dpAfter + cost[i - 1])
    dpBefore = dpAfter
    dpAfter = dpi
  }
  return dpAfter
}

Rust

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let mut dp = vec![0; cost.len() + 1];
        for i in 2..=cost.len() {
            dp[i] = (dp[i - 1] + cost[i - 1]).min(dp[i - 2] + cost[i - 2]);
        }
        dp[cost.len()]
    }
}

不使用 dp 数组

impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let (mut dp_before, mut dp_after) = (0, 0);
        for i in 2..=cost.len() {
            let dpi = (dp_before + cost[i - 2]).min(dp_after + cost[i - 1]);
            dp_before = dp_after;
            dp_after = dpi;
        }
        dp_after
    }
}

C

#include <math.h>
int minCostClimbingStairs(int *cost, int costSize) {
  int dp[costSize + 1];
  dp[0] = dp[1] = 0;
  for (int i = 2; i <= costSize; i++) {
    dp[i] = fmin(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
  }
  return dp[costSize];
}

不使用 dp 数组

#include <math.h>
int minCostClimbingStairs(int *cost, int costSize) {
  int dpBefore = 0, dpAfter = 0;
  for (int i = 2; i <= costSize; i++) {
    int dpi = fmin(dpBefore + cost[i - 2], dpAfter + cost[i - 1]);
    dpBefore = dpAfter;
    dpAfter = dpi;
  }
  return dpAfter;
}

Scala

object Solution {
  def minCostClimbingStairs(cost: Array[Int]): Int = {
    var dp = new Array[Int](cost.length)
    dp(0) = cost(0)
    dp(1) = cost(1)
    for (i <- 2 until cost.length) {
      dp(i) = math.min(dp(i - 1), dp(i - 2)) + cost(i)
    }
    math.min(dp(cost.length - 1), dp(cost.length - 2))
  }
}

第二种思路: dp[i] 表示爬到第i-1层所需的最小花费,状态转移方程为: dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

object Solution {
  def minCostClimbingStairs(cost: Array[Int]): Int = {
    var dp = new Array[Int](cost.length + 1)
    for (i <- 2 until cost.length + 1) {
      dp(i) = math.min(dp(i - 1) + cost(i - 1), dp(i - 2) + cost(i - 2))
    }
    dp(cost.length)
  }
}

C#

public class Solution
{
    public int MinCostClimbingStairs(int[] cost)
    {
        int[] dp=new int[2] { cost[0], cost[1] };
        for (int i = 2; i < cost.Length; i++)
        {
            int temp = Math.Min(dp[0], dp[1])+cost[i];
            dp[0]=dp[1];
            dp[1]=temp;
        }
        return Math.Min(dp[0],dp[1]);
    }
}