题解 | 最小花费爬楼梯

import java.util.*;


public class Solution {
    /**
     * 到达第 n 级台阶的花费有两种情况 1.从第 n-1级台阶来，费用等于到达 n-1级台阶的花费 + cost[n-1];2.从第 n-2 级台阶来，费用等于到达 n-2 级台阶的花费 + cost[n-2],求两者最小值
     * minCost(n) = Math.min(minCost(n-1) + cost(n-1),minCost(n-2) + cost(n-2))，所以可以递归求解
     * <p>
     * 另外可以使用一个数组来记录已经计算过的值，避免重复计算
     * arr[0] = 0、arr[1] = 0 、arr[2] = min(arr[0] + cost(0),arr[1] + cost(1))
     * 这样就可以使用动态规划求解
     */
    public int minCostClimbingStairs(int[] cost) {
        if (cost == null || cost.length <= 1) {
            return 0;
        }

        int[] arr = new int[1000000];
        arr[0] = 0;
        arr[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            arr[i] = Math.min(arr[i - 1] + cost[i - 1], arr[i - 2] + cost[i - 2]);
        }
        return arr[cost.length];
    }
}