【数据结构和算法】最小花费爬楼梯

解法一

如果到第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];
    }
}

解法二

上面代码我们还可以优化一下，因为计算当前位置的时候只和他前面的两个位置有关，所以我们可以不需要dp数组，直接使用几个变量即可，代码如下

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 first = 0;
        int second = 0;
        int third = 0;

        for (int i = 2; i <= cost.length; i++) {
            third = Math.min(first + cost[i - 2], second + cost[i - 1]);
            first = second;
            second = third;
        }
        return third;
    }
}