牛客网真题2019-37-最小代价爬楼梯

递归：超时长

动态规划 dp:dp[n]=min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])
值得注意的是本题是跳过第n阶，从n或者n-1到达 第n+1，所以sout(dp[n+1])

import java.util.Scanner;
public class Main {
  public static int step(int[] cost, int i){
      if(i <= 1){
          return 0;
      }
      return Math.min(step(cost, i - 1) + cost[i - 1], step(cost, i - 2) + cost[i - 2]);
  }

  public static void main(String[] args){
      Scanner scanner = new Scanner(System.in);
      String[] s = scanner.nextLine().split(",");
      int[] cost = new int[s.length + 1];
      for(int i = 1; i < cost.length; i++){
          cost[i] = Integer.parseInt(s[i - 1]);
      }
      //        System.out.println(step(cost, s.length + 1));
      int[] dp = new int[cost.length + 1];
      dp[0] = 0;
      dp[1] = 0;

      for(int i = 2; i < dp.length; i++){
          dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
      }
      System.out.println(dp[dp.length - 1]);
  }
}