题解 | 最小花费爬楼梯

如果到第i个台阶，我们可以从第i-1个台阶跳一步上来，也可以从第i-2个台阶跳两步上来。哪个花费少我们就选择从哪个跳上来。我们定义dp[i]表示到第i个台阶需要的最小花费，那么我们可以得出递推公式

dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

其中

• dp[i - 2] + cost[i - 2]表示从第i-2个台阶跳到第i个台阶的最小花费
• dp[i - 1] + cost[i - 1]表示从第i-1个台阶跳到第i个台阶的最小花费

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];
    }
}