最小代价爬楼梯

[编程题]最小代价爬楼梯

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

你需要爬上一个 n 层的楼梯，在爬楼梯过程中，每阶楼梯需花费非负代价，第i阶楼梯花费代价表示为 cost[i] ，一旦你付出了代价，你可以在该阶基础上往上爬一阶或两阶。

你可以从第 0 阶或者第 1 阶开始，请找到到达顶层的最小的代价是多少。

n 和 cost[i] 皆为整数

数据范围： $2 \le n \le 1000 \$ , $0 \le cost_i \le 1000 \$

输入描述:

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

10,15,20

输出描述:

输出一个整数，表示花费的最小代价

示例1

输入

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

输出

算法知识视频讲解

Java

牛客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届软工代言人

补充一下测试用例：输入10,1,15,1,1,20 输出3 。由此可见 cost = 20，不是顶层，而是 n - 1 层

发表于 2021-08-20 10:55:14 回复(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)

Java

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

我只想安心搬砖

dp，我也感觉题目意思不明，dp[i]记录的是踏上当前台阶i之前最小的花费，所以递推式

dp[i]=min(dp[i-1]+a[i-1],dp[i-2]+a[i-2])。a记录的花费。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String[] split = s.split(",");
            int[] a = new int[split.length];
            for (int i = 0; i < split.length; i++)
                a[i] = Integer.parseInt(split[i]);
            int[] dp = new int[a.length + 1];
            dp[0] = 0;
            dp[1] = 0;
            for (int i = 2; i < dp.length; i++) {
                dp[i] = Math.min(dp[i - 1] + a[i - 1], dp[i - 2] + a[i - 2]);
            }
            System.out.println(dp[dp.length-1]);
        }

    }

}

发表于 2019-08-16 10:46:30 回复(0)