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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] costs) {
        // write code here
        // 算法核心：从【递归回溯尝试】优化到【记忆化搜素】（因为装填转移只有2个，因此效率与动态规划类似）
        // dp表默认初始化全-1
        int[] dp = new int[costs.length + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        // 注意，爬到数组刚好越界才算爬完
        int result = process(costs, costs.length, dp);
        return result;
    }

    // 计算爬到第target阶（0开始）的最小花费
    public int process (int[] costs, int target, int[] dp) {
        // 递归出口
        if (target == 0) {
            // 爬到第0阶台阶的最小花费
            // 为0，因为可以直接从0开始爬
            dp[0] = 0;
            return dp[0];
        }
        if (target == 1) {
            // 爬到第1阶台阶的最小花费
            // 为0，因为可以直接从1开始爬
            dp[1] = 0;
            return dp[1];
        }

        // 分支尝试

        // 本题状态的转移是【有限个】的，即【不依赖for循环】列举进行状态转移
        // 因此，【记忆化搜索】与【经典动态规划】的时间复杂度【近似】

        // 如果dp表中有计算好的值，则可直接返回
        if (dp[target] != -1) {
            return dp[target];
        }
        // 上了一个台阶到达target位置
        if (dp[target - 1] == -1) {
            // dp表中无值
            dp[target - 1] = process(costs, target - 1, dp);
        }
        int one = dp[target - 1] + costs[target - 1];
        
        // 上了两个台阶到达target位置
        if (dp[target - 2] == -1) {
            // dp表中无值
            dp[target - 2] = process(costs, target - 2, dp);
        }
        int two = dp[target - 2] + costs[target - 2];

        // 记录本位置dp值
        dp[target] = Math.min(one, two);
        return dp[target];
    }
}