首页 > 试题广场 >

最小花费爬楼梯

[编程题]最小花费爬楼梯

热度指数：57491 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的值满足 $1 \le cost_i \le 10^4 \$

示例1

输入

[2,5,20]

输出

说明

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5

示例2

输入

[1,100,1,1,1,90,1,1,80,1]

输出

说明

你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

算法知识视频讲解

牛客575499364号

没有太理解题意，拿[2,5,20]来举例，不是可以从0出发，付2块钱，走2步直接到末尾吗？为啥答案是5？

发表于 2022-03-08 13:19:44 回复(7)

Java

键盘都敲坏了.

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        if(cost.length == 1) return cost[0];
        
        // 初始化两个变量， dp1 = 下标为0的台阶，需要花费， dp2 = 下标为1的台阶，需要花费
        int dp1 = cost[0], dp2 = cost[1];
        
        // 遍历cost数组，从下标2开始
        for (int i = 2; i < cost.length; i++) {
            // 暂存dp2，因为dp1和dp2的花费需要向后移动，所以dp1的花费需要切换到 dp2
            int temp = dp2;
            // 将当前i层台阶的花费 + dp1花费， 与  当前i层台阶的花费 + dp2花费 取最小花费值 赋给dp2
            // 即当达到下标为i层台阶的时候，花费为 (当前i层台阶的花费 + dp1花费， 与  当前i层台阶的花费 + dp2花费 取最小花费值)
            dp2 = Math.min(cost[i] + dp1, cost[i] + dp2);
            // 然后dp1的花费后移，改为之前的dp2
            dp1 = temp;
        }
        // 循环结束时，对比dp1 和 dp2的花费 取最小值
        return dp1 > dp2 ? dp2 : dp1;
    }
}

发表于 2022-11-20 11:44:28 回复(0)

C++

Spectre_

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // 时间复杂度O(N)，空间复杂度O(1)
        int dp0 = 0, dp1 = 0, dp2;
        for (int i = 2; i <= cost.size(); ++i) {
            dp2 = min(dp0 + cost[i - 2], dp1 + cost[i - 1]);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp2;
    }
};

发表于 2022-10-30 20:25:10 回复(0)

Java

Machies201904031152992

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        if (cost.length == 1) return cost[0];
        int first=cost[0],second=cost[1];
        for (int i=2;i<cost.length;i++)
        {
            int temp=second;
            second=Math.min(first+cost[i],second+cost[i]);
            first=temp;
        }
        return first < second ? first : second;
    }
}

发表于 2022-03-13 14:27:04 回复(0)

JavaScript Node

牛客534362463号

function minCostClimbingStairs( cost ) {
    // write code here
    const dp = [];
    dp[0] = 0; dp[1] = 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];
}

发表于 2022-12-06 22:07:53 回复(0)

C++

陈让然

层数i 0 1 2 3 4 5 6 7 8

cost 1 100 1 1 1 90 1 1 80

总花费dp

 int minCostClimbingStairs(vector<int>& cost) 
    {
        // write code here
        //求有多少阶梯
        int n = cost.size();
        //dp用来保存到达对应层阶梯所需的花费
        vector<int> dp(n);
        dp[0] = cost[0];
        dp[1] = cost[1];
        //保存每层所需花费
        for (int i = 2; i < n; i++) 
        {
            dp[i] = cost[i] + min(dp[i-1], dp[i-2]);
        }
        /*
            要么已经登顶dp[n-1]
            要么再爬一层登顶dp[n-2]
            看两者谁花费最少
        */
        return min(dp[n-1], dp[n-2]);

发表于 2023-11-07 15:47:59 回复(0)

Python3

LeoAlan

# 解法一
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化一个dp数组，数组的值为走到这一步所需的花费，数组的长度为n+1，因为最终要走出去
        dp = [0] * (n + 1)
        # 从第一步开始走，所以dp[0]和dp[1]都为0，因为不需要花费，所以从第二步开始，所以从下标2开始遍历，到n+1结束
        for i in range(2, n + 1):
            # 当前花费为（从上一步走来的花费加上之前的花费）或者（从上上一步走来的花费加上之前的花费），取最小值
            dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2])

        return dp[-1]


# 解法二
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 初始化一个dp数组，数组的值为走到这一步所需的再加上走出这一步所需的总花费
        dp = [0] * n

        dp[0:2] = cost[0:2]

        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

        # 最后一步可以选择从倒数第一步走出去，或者从倒数第二步走出去，取最小值
        return min(dp[-1], dp[-2])

发表于 2023-10-14 18:12:21 回复(0)

Java

做则必成的勇气和信心

public int minCostClimbingStairs (int[] cost) {
        int[] dp=new int[cost.length+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<cost.length+1;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

发表于 2023-07-11 17:24:44 回复(0)

Java

daydaylast

import java.util.*;

public class Solution {
    public int minCostClimbingStairs (int[] cost) {
        int n = cost.length;
        if (n <= 1) return cost[0];
        int a = cost[0], b = cost[1], c = 0;
        for (int i = 2; i < n; i++) {
            c = Math.min(a, b) + cost[i];
            a = b;
            b = c;
        }
        return Math.min(a, b);
    }
}

发表于 2023-03-05 19:49:16 回复(0)

C++

pein531

注意顶部是索引为 $n$ 的位置，很常规的一道线性 $DP$ 问题，分别从0和1开始进行 $DP$ 即可，返回这两种策略的代价的较小值。

const int N = 100010;
int dp[N];

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // write code here
        n = cost.size();
        memset(dp, -1, 4*n);
        int res1 = dfs(cost, 0);
        memset(dp, -1, 4*n);
        int res2 = dfs(cost, 1);
        return min(res1, res2);
    }

    int dfs(vector<int>& cost, int cur) {
        if(cur > n) return 0x3f3f3f3f;
        if(cur == n) return 0;
        if(dp[cur] != -1) return dp[cur];
        return dp[cur] = min(dfs(cost, cur + 1), dfs(cost, cur + 2)) + cost[cur];
    }

private:
    int n;
};

发表于 2023-02-07 15:41:10 回复(0)

C++

Frannk+Lin

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int>dp(cost.size()+1); // dp[i]到达i台阶的 最小费用
        dp[0]=0;  //到达 0 和 1 都不需要花费 都是 0 ；
        dp[1]=0;
        for(int i=2;i<=cost.size();i++)
        {
             //到达i有两种方式 每种方式都是 到达自己的最小费用 + 从自己出发的费用
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
};

发表于 2022-12-03 12:49:22 回复(0)

Python3

牛客692053893号

Python 3，动态规划解法

class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        
        # 动态规划
        # 1、确定状态
        # 最后一步前必定是在第i-1级台阶 或 第i-2级台阶
        # 原问题：求通过第i级台阶所花费的最少代价
        # 子问题：求通过第i-1级台阶和通过第i-2级台阶之间花费的最少代价
        # 2、转移方程
        # f(i) = min {f(i-1)+cost(i-1), f(i-2)+cost(i-2)}
        # 3、初始条件
        # 因为可以选择直接从台阶0或台阶1开始爬楼梯，所以: f(0)=0, f(1)=0
        # 4、计算顺序
        # 从小到大依次计算
        # 5、编程实现
        n = len(cost)    # 有n级台阶
        f = [0]*(n+1)    # 台阶从0开始，所以索引n为楼梯顶部，即有n+1级台阶
        for i in range(2, n+1): # 按从小到大的顺序计算
            f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
        return f[n]

发表于 2022-08-26 22:48:37 回复(0)

C++

牛客990046272号

vector<int> dp(cost.size() + 1);
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()];

发表于 2022-08-08 10:23:19 回复(0)

秋叶原の黑猫

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

发表于 2022-06-12 20:58:33 回复(0)

Python 3

我是赵同学

状态转换就OK了

class Solution:
    def minCostClimbingStairs(self , cost: List[int]) -> int:
        # write code here
        n=len(cost)
        if n==1:
            return cost[0]
        c0 = 0   #到第0层最小花销
        c1 = 0   #到第1层最小花销
        
        for i in range(2,n+1):  #要走出最后一个台阶,所以n+1
            c0,c1 = c1,min(c0+cost[i-2],c1+cost[i-1])
            
        return c1

发表于 2022-04-09 15:57:28 回复(0)

Java

只要三星剑姬

public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length];
        dp[dp.length - 1] = cost[dp.length - 1];
        dp[dp.length - 2] = Math.min(cost[dp.length - 2], cost[dp.length - 2] + cost[dp.length - 1]);
        for (int i = dp.length - 3; i >= 0; i--) {
            dp[i]=cost[i]+Math.min(dp[i+1],dp[i+2]);
        }
        return Math.min(dp[0],dp[1]);
    }

发表于 2022-03-16 21:10:16 回复(1)

Python3

lintoon

class Solution:

def minCostClimbingStairs(self , cost: List[int]) -> int:

# write code here

nn=len(cost)

dp=[0*i for i in range(nn+1)]

dp[1]=cost[0]

dp[2]=min(cost[0],cost[1])

dp[3]=min(cost[1],cost[0]+cost[2])

for n in range(4,nn+1):

dp[n]=min(dp[n-2]+cost[n-2],dp[n-1]+cost[n-1])

return dp[nn]

编辑于 2024-04-15 17:16:16 回复(0)

Unknownsun

不需要开辟额外空间

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cost int整型一维数组
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        for (int i = cost.length - 3; i >= 0; i--) {
            cost[i] = cost[i] + Math.min(cost[i + 1], cost[i + 2]);
        }
        return Math.min(cost[0],cost[1]);
    }
}

编辑于 2024-04-10 22:28:34 回复(0)

Leeston520

脑溢血解法：

public int minCostClimbingStairs(int[] cost) {
        // write code here
        if (cost.length == 1)
            return 0;
        else if (cost.length == 2)
            return Math.min(cost[0], cost[1]);
        else if (cost.length == 3)
            return Math.min(cost[0] + cost[2], cost[1]);
        else
            return Math.min(
                    minCostClimbingStairs(Arrays.copyOfRange(cost, 0, cost.length - 1)) + cost[cost.length - 1],
                    minCostClimbingStairs(Arrays.copyOfRange(cost, 0, cost.length - 2)) + cost[cost.length - 2]
            );
    }

正确解法：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cost int整型一维数组
     * @return int整型
     */
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length == 1) return 0;
        int dp1 = cost[0], dp2 = cost[1];
        // 关键点: 计算当前台阶的总花费时，它相当于上一层台阶的花费
        for (int i = 2; i < cost.length; i++) {
            /* 举例：
             * 当爬到第三层台阶的是，总花费可以解释为：
             * 如果从1台阶开始，则是 1台阶和3台阶花费，
             * 如果是2台阶开始，没必要计算3层台阶花费，
             * 因为2层可以直接爬到4层
             *
             * TODO: 理解难点 --> 为什么要将当前的 dp1 的值置为开始 dp2 的值？
             *      答： 当前循环中，dp2 计算后是当前的总花费，dp2计算前则是上一层的总花费
             *      就使用到了 temp 来跟进计算前的值，并赋值给 dp1 表示下一层循环中，n-2的总花费
             *      下一层循环中 n -1 的总花费则是 dp2,也是计算前上一层的总花费
             */
            int temp = dp2;

            dp2 = Math.min(cost[i] + dp1, cost[i] + dp2);
            dp1 = temp;
        }
        return Math.min(dp1, dp2);
    }
    }

编辑于 2024-04-04 11:06:10 回复(0)

一个优雅的程序猿

#define min(a,b)   (a>b ? b : a)
int minCostClimbingStairs(int* cost, int costLen ) {
    int res[100001], i;
    res[0] = 0;
    res[1] = 0;
    for(i=2; i<=costLen; i++)
    res[i] = min(res[i-1]+cost[i-1], res[i-2]+cost[i-2]);
    return res[costLen];
}

编辑于 2024-03-23 22:53:44 回复(0)