首页 > 试题广场 >

最小花费爬楼梯

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

热度指数：12875 时间限制：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 \$

输入描述:

第一行输入一个正整数 n ，表示数组 cost 的长度。
第二行输入 n 个正整数，表示数组 cost 的值。

输出描述:

输出最低花费

示例1

输入

3
2 5 20

输出

说明

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

示例2

输入

10
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 。

算法知识视频讲解

Gargantua

#include<stdlib.h>
#include<algorithm>
using namespace std;

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int *cost=(int *)malloc(sizeof(int)*(n+2));
		int *dp=(int *)malloc(sizeof(int)*(n+2));
		for(int i=1;i<=n;i++){
			scanf("%d",&cost[i]);
		}
		dp[1]=0;
		dp[2]=0;
		dp[3]=min(dp[1]+cost[1],dp[2]+cost[2]);
		for(int i=4;i<=n+1;i++)
			dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
		printf("%d\n",dp[n+1]);
	}
	return 0;
}

发表于 2022-03-21 20:03:42 回复(0)

C++

Spectre_

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n < 2) {
        cout << 0;
        return 0;
    }
    int arr[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    // 时间复杂度O(N)，空间复杂度O(1)
    int dp0 = 0, dp1 = 0, dp2;
    for (int i = 2; i <= n; ++i) {
        dp2 = min(dp0 + arr[i - 2], dp1 + arr[i - 1]);
        dp0 = dp1;
        dp1 = dp2;
    }
    cout << dp2;
    return 0;
}

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

牛客嗷嗷

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int []arr = new int[n + 1];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();

        int []dp = new int[n + 1];
        dp[0] = dp[1] = 0;

        for (int i = 2; i <= n; i++)
            dp[i] = Math.min(dp[i - 1] + arr[i - 1], dp[i - 2] + arr[i - 2]);

        System.out.println(dp[n]);
    }
}

发表于 2022-09-27 18:11:30 回复(0)

matlab

LuckyYing

% 运行超时

% 您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

% 虽然报错但是这个代码已经不能再进一步优化了

clc

clear

N = input(''); % 下标从 0 开始

all_ladder = N+1; % 总台阶数

cost = str2num(input('', 's')); % 花费清单

dp_i_1 = 0;

dp_i_2 = 0;

for i = 3:all_ladder

if dp_i_1 + cost(i-1) < dp_i_2 + cost(i-2)

dp_i = dp_i_1 + cost(i-1);

else

dp_i = dp_i_2 + cost(i-2);

end

dp_i_2 = dp_i_1;

dp_i_1 = dp_i;

end

fprintf('%d', dp_i)

编辑于 2024-01-27 16:25:42 回复(0)

o同学

为啥2,5,20这个答案是5不是2？？？

发表于 2023-10-21 19:16:12 回复(1)

dsada_

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int MinCost(vector<int> a, int n){

if(n<2) return min(a[0],a[1]);

else{

vector<int> allmincost(n+1,0);

allmincost[0] = a[0];

allmincost[1] = a[1];

for(int i = 2;i<n;++i){

allmincost[i] = min(allmincost[i-1],allmincost[i-2])+a[i];

}

return min(allmincost[n-2],allmincost[n-1]);

}

int main(){

int n;

cin >> n;

vector<int> a(n);

for(int i =0;i<n;++i){

cin >> a[i];

}

cout<<MinCost(a, n)<<endl;

}

发表于 2023-10-10 23:33:41 回复(0)

C++

牛客541678616号

设dp为最小到该位置的最小花费，然后只看前两阶就行了

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int st[n+1];
    int cost[n+1];
    for(int i=0;i<n;i++)
    {
        cin>>st[i];
        cost[i]=0x3f3f3f3f;
    }
    cost[n] = 0x3f3f3f3f;
    cost[1]=cost[0]=0;
    for(int i=0;i<=n;i++)
    {
        for(int s=i-2;s<i;s++)
        {
            if(s<0)continue;
            cost[i]=min(cost[i],cost[s]+st[s]);
        }
    }
    cout<<cost[n];
}

发表于 2023-08-30 17:08:02 回复(0)

Python3

化骨重生

import sys

n=int(input())

L=list(map(int,input().split()))

if n==1:

print(L[0])

elif n==2:

print(min(L[0],L[1]))

else:

for i in range(2,n):

L[i]+=min(L[i-1],L[i-2])

print(min(L[n-1],L[n-2]))

发表于 2023-04-17 22:59:22 回复(0)

Javascript

海若有因_

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let n = (await readline()).split(" ")[0];
    let stairs = (await readline()).split(" ");
    let arr = []
    stairs.forEach(e => {
        arr.push(parseInt(e))
    })
    
    function minCost(num, cost) {
        if(num == 1) {
            return 0
        }
        let res = new Array(n)
        res[num - 1] = 0
        res[num - 2] = cost[num - 2] < cost[num - 1] ? cost[num - 2]:cost[num - 1]
        for(let i = num - 3; i >= 0; i--) {
            if(cost[i] + res[i + 1] <= cost[i + 1] + res[i + 2]) {
                res[i] = cost[i] + res[i + 1]
            }
            else {
                res[i] = cost[i + 1] + res[i + 2]
            }
        }
        return res[0]
    }
    
    console.log(minCost(n, arr));
})();

js解题方法：创建长度为num的答案数组res，res[num-1] = 0，然后从楼梯长度为2时（即仅考虑最后两级楼梯）开始求解，答案存储在res[num - 1]，逐渐增加楼梯长度至n，即计算res[0]。最后返回res[0]

发表于 2023-03-31 17:44:36 回复(0)

Python3

Ghost星雲

n = int(input())

cost = input().split()

f = [0,0]

for i in range(2,n+1):

f.append(min(int(cost[i-2])+f[i-2],int(cost[i-1])+f[i-1]))

print(f[n])

发表于 2023-03-26 14:20:50 回复(0)

努力学好算法的小白

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] cost = new int[in.nextInt()];
        for(int i = 0;i<cost.length;i++){
            cost[i] = in.nextInt();
        }
        int result = ComputeMinCost(cost);
        System.out.println(result);
    }

    public static int ComputeMinCost(int[] cost){
        //定义dp数组
        int length = cost.length;
        int[] dp  = new int[length+1];
        //初始化dp数组
        dp[0] = 0;
        dp[1] = 0;
        //遍历数组
        for(int i =2;i<=length;i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1]  , dp[i-2] + cost[i-2] );

        }
        return dp[length];
    }



}

发表于 2023-02-28 10:30:29 回复(0)

ultra鲤鱼

#include <stdio.h>
#include <string.h>
#define MaxCost 1000000
int jumpStep(int* cost,int costLen);
int main() {
    int cost[MaxCost];
    int costLen = 0;
    while(scanf("%d",&costLen)!=EOF){
        memset(cost,0,sizeof(int)*costLen);
        int i = 0;
        for(i = 0;i < costLen;i++)
            scanf("%d",&cost[i]);
        int result = 0;
        result = jumpStep(cost, costLen);
        printf("%d\n",result);
    }
    return 0;
}
int jumpStep(int* cost,int costLen){
    if(costLen == 1 || costLen == 2)
    return 0;
    int dp[MaxCost];
    memset(dp,0, costLen*sizeof(int));
    dp[0] = 0;
    dp[1] = 0;
    int i = 0;
    for(i = 2; i<costLen;i++){
        dp[i] = dp[i-1]+cost[i-1]<dp[i-2]+cost[i-2]?dp[i-1]+cost[i-1]:dp[i-2]+cost[i-2];
    }
    return dp[costLen-1]+cost[costLen-1]<dp[costLen-2]+cost[costLen-2]?dp[costLen-1]+cost[costLen-1]:dp[costLen-2]+cost[costLen-2];
}

发表于 2023-02-27 11:41:57 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scanf("%d",&n)
    var arr []int
    var x int
    for n>0{
        fmt.Scanf("%d",&x)
        arr=append(arr,x)
        n--
    }
    if len(arr)==1{
        fmt.Println(arr[0])
        return
    }
    dp:=make([]int,len(arr))
    dp[0]=arr[0]
    dp[1]=arr[1]
    for i:=2;i<len(arr);i++{
        dp[i]=min(dp[i-1],dp[i-2])+arr[i]
    }
    fmt.Println(min(dp[len(dp)-1],dp[len(dp)-2]))
}

func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}

发表于 2023-02-04 10:35:32 回复(0)

喝醉了Ta的梦,晚安

#include <iostream>
using namespace std;
#include <vector>
int a[100005];

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) cin >> v[i];
    for(int i = 2; i <= n; ++i) {
        a[i] = min(a[i-1] + v[i-1], a[i-2] + v[i-2]);
    }
    cout << a[n] << endl;
}
// 64 位输出请用 printf("%lld")

发表于 2023-01-16 22:30:52 回复(0)

蜗牛与风

package main

import (
    "fmt"
)

func main() {
    a := 0
    fmt.Scan(&a)
    cost := make([]int,a + 1)
    for i := 0;i <= a;i++ {
        fmt.Scan(&cost[i])
    }
    dp := make([]int,a + 1)
    dp[0] = 0
    dp[1] = 0
    for i := 2; i <= a;i++ {
        dp[i] = min(dp[i-2] + cost[i-2],dp[i-1] + cost[i-1])
    }
    fmt.Println(dp[a])
}
func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}

发表于 2022-10-25 15:33:38 回复(0)

Java

努力学习ing！！

动态规划，比较好理解

到第n级台阶，可以通过n-1级跳一阶，或者n-2级跳两阶

显然，我们只需要看到达n-1级最小花费加上在n-1级台阶需要花费的

和到n-2最小花费加上在n-2 上花费的哪个更小就是我们想要的

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            int n = Integer.parseInt(s);
            int[] cost = new int[n];
            String[] numStr = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                cost[i] = Integer.parseInt(numStr[i]);
            }
            int[] dp = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
            }
            System.out.println(dp[n]);
        }
    }
}

发表于 2022-10-03 20:15:09 回复(0)

Python 3

梅子酒l

n = int(input())
cost = list(map(int, input().split()))
dp = [0 for _ in range(n+1)]
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
print(dp[n])

发表于 2022-09-15 20:06:45 回复(0)

Javascript_V8

LivingRose

while(n = +readline()){
   var lines = readline().split(' ')
   lines.forEach(function(ele,index){
        lines[index] = +ele;
    });
    var length = lines.length;
    var res = new Array(length+1);
    res[0]=0;
    if(length>0){
        res[1]=0
    }
    for (let i =1;i<length;i++){
        res[i+1] = res[i]+lines[i]>res[i-1]+lines[i-1]?res[i-1]+lines[i-1]:res[i]+lines[i];
        
    }
   // console.log(res)
    console.log(res[length])
}

发表于 2022-09-05 17:45:35 回复(0)

牛客283687938号

谁能够提供一下JavaScript Node怎么读取多行数据呀

发表于 2022-09-01 01:35:31 回复(0)

Java

Hans.1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int[] cost = new int[in.nextInt()];
for (int i = 0; i < cost.length; i++) {
cost[i] = in.nextInt();
}
System.out.println(minCostClimbingStairs(cost));
}

private static int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
for (int i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[cost.length];
}
// public static Map<Integer, Integer> sResultMap = new HashMap<Integer, Integer>();

// public static void main(String args[]) throws Exception{
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// int arrCount = Integer.parseInt(br.readLine());
// String[] arr = br.readLine().split(" ");
// int[] intArr = new int[arr.length];
// for(int i = 0; i < arr.length; i++) {
// intArr[i] = Integer.parseInt(arr[i]);
// }
// int result = func(arr.length, intArr);
// System.out.println(result);
// }

// public static int func(int index, int[] cost) {
// if(sResultMap.get(index) != null) {
// return sResultMap.get(index);
// }
// if(index == 0 || index == 1) {
// return 0;
// }
// int result = Math.min(func(index - 1, cost) + cost[index - 1], func(index - 2, cost) + cost[index - 2]);
// sResultMap.put(index, result);
// return result;
// }
}

发表于 2022-08-24 15:33:22 回复(0)

提交观点

问题信息

动态规划

难度：

31条回答 79收藏 1726浏览

通过挑战的用户

查看代码

KD-7

2022-09-26 21:36:31
牛客53155...

2022-09-16 14:31:31
牛客42043...

2022-09-15 23:55:56
枺翳

2022-09-15 23:51:21
NiimiSora

2022-09-15 22:17:15

最小花费爬楼梯

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题