题解 | #最小花费爬楼梯#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        // int process1 = process(arr, 0, 0);
        // int process2 = process(arr, 1, 0);

        // System.out.println(Math.min(process1, process2));

        System.out.println(dp(arr));
    }

  //尝试方法，超时了
    public static int process(int[] arr, int index, int free) {
        int len = arr.length - 1;
        if (index == len) {
            return free + arr[index];//通过最后一个台阶登顶
        }
      
        if (index > len) {
            return free;//没通过最后一个台阶登顶
        }

        free += arr[index];
        //走一步
        int one = process(arr, index + 1, free);
        //走两步
        int tow = process(arr, index + 2, free);
        //取最小值
        return Math.min(one, tow);
    }

  //动态规划
    public static int dp(int[] arr) {

        int len = arr.length;

        int[] dp = new int[len];

        dp[len - 1] = arr[len - 1];
        dp[len - 2] = arr[len - 2];

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

}