首页 > 试题广场 >

最小代价爬楼梯

[编程题]最小代价爬楼梯
  • 热度指数：9005 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
你需要爬上一个 n 层的楼梯，在爬楼梯过程中， 每阶楼梯需花费非负代价，第i阶楼梯花费代价表示为 cost[i] ， 一旦你付出了代价，你可以在该阶基础上往上爬一阶或两阶。
你可以从第 0 阶或者 第 1 阶开始，请找到到达顶层的最小的代价是多少。
n 和 cost[i] 皆为整数

数据范围： ,

输入描述:
输入为一串半角逗号分割的整数，对应cost数组，例如

10,15,20


输出描述:
输出一个整数，表示花费的最小代价
示例1

输入

1,100,1,1,1,100,1,1,100,1

输出

6
算法知识视频讲解
添加回答
C/C++
卷积神经网络哦头像 卷积神经网络哦
一是读逗号隔开的数据   二是动态规划 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
string s;
int arr[maxn], N, d[maxn];

void read(const string &s){
    string tmp = "";
    N = 0;
    for(int i = 0; i <= s.length(); i++) {
        if(i == s.length() || s[i] == ',') {
            arr[N++] = atoi(tmp.c_str());
            tmp.clear();
		} else {
			tmp.push_back(s[i]);
		}
    }
}

int main(){
    cin>>s; read(s);
	memset(d, 0, sizeof(d));
	d[0] = arr[0]; d[1] = arr[1];
	for(int i = 2; i <= N; i++) 
		d[i] = min(arr[i] + d[i - 1], arr[i] + d[i - 2]);
	cout<<d[N]<<endl;
}
/*
1,100,1,1,1,100,1,1,100,1
*/


发表于 2019-09-01 12:56:25 回复(1)
珞文头像 珞文
输入是真的恶心，就不能直接给个数组吗？像LeetCode那样。
发表于 2019-03-31 18:07:24 回复(3)
叶挽秋头像 叶挽秋

这个NC题目说的不清楚，题目说到达顶层，正常理解就是到达最后一层台阶，但实际上他是要求跳出最后一层台阶，也就是说对于给的例子1,100,1,1,1,100,1,1,100,1来说，依次站立的位置是，0,2,4,6,7,9，最后还要从9这个位置跳出去，所以花费是6。因此使用动态规划求出到达最后一级台阶和倒数第二级台阶所需最小花费时，还要从这两者中取较小者作为跳出所有台阶的结果。真是NC啊。

import java.util.*;
/*
动态规划：
dp[i]表示到达第i层台阶赋初的最小代价
那么dp[i] = cos[i] + min(dp[i-1], dp[i-2]);
*/
public class Main {
    public static void main(String[] args) {
        // 获取输入
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        String[] cosStr = input.split(",");
        int N = cosStr.length;
        int[] cos = new int[N];
        for (int i = 0; i < N; ++i) {
            cos[i] = Integer.parseInt(cosStr[i]);
        }

        int[] dp = new int[N];
        dp[0] = cos[0];
        dp[1] = cos[1];
        for (int i = 2; i < N; ++i) {
            dp[i] = cos[i] + (dp[i-1] < dp[i-2] ? dp[i-1] : dp[i-2]);
        }

        System.out.println(dp[N-1] < dp[N-2] ? dp[N-1] : dp[N-2]);
    }
}
发表于 2020-02-19 12:48:10 回复(1)
Ankang0320头像 Ankang0320
dp解法。题意表述不明，如果是跳上n层台阶，那么n=2时，最少跳0次，因为可以从第1阶出发。而根据测试用例，应该指跳出第n阶，即跳上第n+1阶。dp[0]=0，dp[1]=[0]，dp[i]=min(dp[i-1]+costs[i-1],dp[i-2]+costs[i-2])，一直递推到dp[n]即可。 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> costs;
    int temp;
    char c;
    while(1)
    {
        cin>>temp;//获取一个数字
        costs.push_back(temp);//放入数组
        cin.get(c);//获取字符
        if(c=='\n')//如果为换行符
            break;//退出
    }
    int n=costs.size();//总的台阶数目
    vector<int> dp(n+1,0);//跳上第n阶（从0开始）所需的最小代价
    //dp[0]=0 从0阶出发
    //dp[1]=0 从1阶出发 初始值在初始化dp数组时可以一并赋值
    for(int i=2;i<=n;i++)
        dp[i]=min(dp[i-1]+costs[i-1],dp[i-2]+costs[i-2]);//由第i-1或i-2阶跳
    cout<<dp[n]<<endl;//输出跳上第n+1阶所需最小代价
    return 0;
}

发表于 2019-07-17 15:36:50 回复(3)
小小呆萌坤头像 小小呆萌坤
动态规划 
思路: 爬上台阶dp[n] 有两种情况 
第一种 从 dp[n-1]爬上来, 第二种 从 dp[n-2]爬上来,
因此通项公式 dp[n] = min{dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]} 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    class Program
    {
        public static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
        }

        public static void Func(string line)
        {
            var cost = line.Split(',').Select(x => int.Parse(x)).ToArray();
            int n = cost.Length;
            int[] dp = new int[n+1];
            for (int i = 2; i <= n; i++)
            {
                dp[i] = Math.Min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
            }
            Console.WriteLine(dp[n]);
        }
    }
}

发表于 2019-12-05 18:04:37 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int x;
    vector<int> v;
    char c;
    while(cin>>x){
        v.push_back(x);
        cin>>c;
        if(c=='\n')
            break;
    }
    int n = v.size();
    int dp[n+1];
    dp[0] = v[0];
    dp[1] = v[1];
    for(int i=2;i<=n;i++)
        dp[i] = min(dp[i-1], dp[i-2]) + v[i];
    cout<<dp[n]<<endl;
    return 0;
}

发表于 2019-11-04 02:39:16 回复(0)
C/C++
昔遥暮云头像 昔遥暮云 
//动态规划：
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> arr;
    while(1){
        int t;
        cin>>t;
        arr.push_back(t);
        if(cin.get()=='\n')
            break;
    }
    int n=arr.size();
    vector<int> dp(n+1,0);
    dp[0]=arr[0];
    dp[1]=arr[1];
    for(int i=2;i<=n;i++){
        dp[i]=min(dp[i-1],dp[i-2])+arr[i];
    }
    cout<<dp[n];
    return 0;
}

//空间压缩版：
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> arr;
    int Min,pre=0,ppre=0;
    while(1){
        int cur;
        cin>>cur;
        Min=min(pre,ppre)+cur;
        if(cin.get()=='\n'){
            Min=min(pre,Min);
            break;
        }
        ppre=pre;
        pre=Min;
    }
    cout<<Min;
    return 0;
}

发表于 2019-10-20 11:09:46 回复(0)
freezerhan头像 freezerhan 
#include <bits/stdc++.h>

using namespace std;

vector<int> cost;
int f[1002];

void read(vector<int> &v){
  int num = 0;
  char c;
  v.push_back(0);
  while((c = getchar()) != '\n'){
    if(c != ','){
      num = 10 * num + c - '0';
    } else {
      v.push_back(num);
      num = 0;
    }
  }
  v.push_back(num);
  v.push_back(0);
}

int main(){
  read(cost);
  f[0] = cost[0];
  f[1] = cost[1];
  for (int i = 2; i < cost.size(); i++){
    f[i] = min(f[i - 1], f[i - 2]) + cost[i];
  }
  cout << f[cost.size() - 1] << "\n";
  return 0;
}

发表于 2019-09-12 08:41:12 回复(0)
Python
ElonB头像 ElonB 
"""
台阶问题，考虑动态规划
设dp[i]为到达第i层的最小花费，
dp[i] = min(dp[i - 1], dp[i - 2]) + a[i]
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split(',')))
    a.append(0)
    dp = [a[0], a[1]]
    for i in range(2, len(a)):
        dp.append(min(dp[i - 1], dp[i - 2]) + a[i])
    print(dp[-1])

发表于 2019-07-10 14:47:23 回复(0)
Java
lmz9509头像 lmz9509 
/*

*/
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.next();
        //字符串将‘，’取出后的字符数组
        String[] arr = str.split(",");
        int[] cost = new int[arr.length];
        //字符数组转为int数组
        for(int i = 0;i<arr.length;i++){
            cost[i] = Integer.parseInt(arr[i]);
        }
        //判断是从第一阶还是第0阶开始
        int step = 0;
        int sum = cost[0];
        if(cost[0]>=cost[1]){
            step = 1;
            sum = cost[1];
        }
        while(step<cost.length-2){
            int test1 = cost[step] + cost[step+1];
            int test2 = cost[step] + cost[step+2];
            if(test1>=test2){
                sum+=cost[step+2];
                step+=2;
            }else{
                sum+=cost[step+1];
                step++;
            }
        }
        System.out.println(sum);
    }
}
有没有大神能帮我看看，我这种方法怎么会不能完全通过呢？
发表于 2020-04-19 11:37:01 回复(0)
Java
牛客835338448号头像 牛客835338448号 
import java.util.Scanner;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            // 输入的处理，真是麻烦，还好有流处理
            String nStr = in.nextLine();
            int[] cost = Arrays.stream(nStr.split(",")).mapToInt(Integer::parseInt).toArray();
            int n = cost.length;
            // f(i): 到第 i 层的最小代价
            // f(i) = min{f(i - 1) + cost[i - 1], f(i - 2) + cost[i - 2]}
            // f(0) = 0, f(1) = 0
            int[] dp = new int[2];
            for (int i = 2; i <= n; i++) {
                dp[i % 2] = Math.min(dp[(i - 1) % 2] + cost[i - 1], dp[(i - 2) % 2] + cost[i - 2]);
            }
            System.out.println(dp[n % 2]);
        }
    }
}

发表于 2022-10-12 17:14:01 回复(0)
Java
科大15届软工代言人头像 科大15届软工代言人
补充一下测试用例：输入10,1,15,1,1,20  输出3 。由此可见 cost = 20，不是顶层，而是 n - 1 层
发表于 2021-08-20 10:55:14 回复(0)
wzq_985头像 wzq_985
以下是我的代码，只通过了88.89%，求大佬帮忙看看哪里出问题了
cost = list(map(int, input().split(',')))
def dp(c):
    if len(c)> 2:
        return min(dp(c[:-1])+c[-1],dp(c[:-2])+c[-2])
    if len(c) == 1:
        return 0
    if len(c) == 2:
        return min(c[0],c[1])
print(dp(cost))
编辑于 2020-10-30 11:48:14 回复(0)
ADPX丶头像 ADPX丶 
import java.util.*;

public class Main{
    
    public static void main(String[] args){
    
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] ss = s.split(",");
        int[] nums = new int[ss.length];
        for(int i = 0; i < nums.length; i++){
            nums[i] = Integer.parseInt(ss[i]);
        }
        int ans = solution(nums);
        System.out.println(ans);
    }
    
    private static int solution(int[] nums){
        
        int pp = 0, p = 0;
        int min = 0;
        
        for(int num : nums){
            
            pp = p;
            p = min;
            min = Math.min(pp,p) + num;
        }
        return Math.min(min,p);
    }
}

发表于 2020-06-30 00:37:03 回复(0)
Java
叮咚片头像 叮咚片
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strmun = str.trim().split(",");

        // System.out.println(Arrays.toString(strmun));
        if (strmun.length == 1) {

            System.out.println(Integer.valueOf(strmun[0]));

            return;
        }

        if (strmun.length == 2) {

            if (Integer.valueOf(strmun[0]) > Integer.valueOf(strmun[1])) {

                System.out.println(Integer.valueOf(strmun[1]));
            } else {

                System.out.println(Integer.valueOf(strmun[0]));
            }

            return;
        }

        int[] dp = new int[strmun.length];

        dp[0] = Integer.valueOf(strmun[0]);
        dp[1] = Integer.valueOf(strmun[1]);
        int i;
        for (i = 2; i < strmun.length; i++) {

            if (Integer.valueOf(strmun[i]) + dp[i - 1] > Integer.valueOf(strmun[i]) + dp[i - 2]) {
                dp[i] = Integer.valueOf(strmun[i]) + dp[i - 2];

            } else {
                dp[i] = Integer.valueOf(strmun[i]) + dp[i - 1];
            }
        }

        System.out.println(Arrays.toString(dp));
        if (dp[i - 1] < dp[i - 2])
            System.out.println(dp[i - 1]);
        else {
            System.out.println(dp[i - 2]);
        }

    }

}
发表于 2020-05-31 12:05:09 回复(0)
良17头像 良17 
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strArray = str.split(",");
        int n = strArray.length;
        int[] array = new int[n];
        for(int i=0;i<n;i++){
            array[i] = Integer.parseInt(strArray[i]);
        }
        int[] sum = new int[n+1];
        sum[0] = 0;
        sum[1] = 0;       
        for(int i =2;i<=n;i++){
            int a = sum[i-1] + array[i-1];
            int b = sum[i-2] + array[i-2];
            sum[i] = Math.min(a,b);       
        }
        
        System.out.println(sum[n]);
        
    }
}

发表于 2020-02-20 22:28:22 回复(0)
Python
外包不准吃公司零食头像 外包不准吃公司零食

Python 动态规划

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

注意可以花费0代价调到第0或第1层 


import sys
L = list(map(int, sys.stdin.readline().strip().split(',')))
if len(L)<=2:
    print(min(L))
else:
    dp = [0]*len(L)
    for i in range(2, len(L)):
        dp[i] = min(dp[i-1]+L[i-1], dp[i-2]+L[i-2])
    print(min(dp[-1]+L[-1], dp[-2]+L[-2]))


编辑于 2020-02-17 22:30:21 回复(0)
lhyAira头像 lhyAira 
            string input = string.Empty;
            while (!string.IsNullOrEmpty(input = Console.ReadLine()))
            {
                int[] cost = input.Split(',').Select(x => int.Parse(x)).ToArray();
                int length = cost.Length;
                int[] f = new int[length];
                f[0] = cost[0];
                f[1] = cost[1];
                if (length == 1)
                {
                    Console.WriteLine(f[0]);
                }
                else if (length == 2)
                {
                    Console.WriteLine(Math.Min(f[0], f[1]));
                }
                else
                {
                    for (int n = 2; n < length; n++)
                    {
                        f[n] = Math.Min(f[n - 1], f[n - 2]) + cost[n];
                    }
                    Console.WriteLine(Math.Min(f[cost.Length - 1], f[cost.Length - 2]));
                }
            }

发表于 2020-01-21 16:41:55 回复(0)
牛客658998号头像 牛客658998号 
cost=list(map(int,input().split(',')))
dp=[0]*(len(cost)+1)
dp[0]=0
dp[1]=0
for i in range(2,len(cost)+1):
    dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
print(dp[-1])

发表于 2019-12-15 10:04:22 回复(0)
1辰头像 1辰 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] t = str.split(",");
        int[] cost = new int[t.length];
        visited = new int[cost.length];
        Arrays.fill(visited, -1);
        for(int i = 0; i < t.length; i ++) {
            cost[i] = Integer.valueOf(t[i]);
        }
        System.out.println(Math.min(dfs(cost, 0), dfs(cost, 1)));

    }
    public static int[] visited;
    public static int dfs(int[] cost, int index) {
        if(index >= cost.length)
            return 0;
        if(visited[index] != -1)
            return visited[index];
        int ans = Math.min(dfs(cost, index + 1) + cost[index], dfs(cost, index + 2) + cost[index]);
        visited[index] = ans;
        return ans;
    }
}

发表于 2019-10-15 22:10:52 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 动态规划 安卓工程师 快手 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 2019 Java工程师
上传者：小小
难度：
37条回答 7833浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号