题解 | 最小花费爬楼梯

import java.util.*;


public class Solution {
 /**
     * 计算爬到顶层的最小成本
     *
     * @param cost 每个台阶对应的费用数组
     * @return 到达顶层的最小成本
     */
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length; // 台阶总数
        int[] memo = new int[n + 1]; // 备忘录数组，用于存储已经计算过的结果
        Arrays.fill(memo, -1); // 初始化备忘录，-1表示未计算
        return dp(cost, n, memo); // 调用动态规划方法求解

    }

    /**
     * 动态规划方法，使用备忘录优化递归
     *
     * @param cost 台阶费用数组
     * @param n    当前要到达的台阶数
     * @param memo 备忘录数组，存储已计算结果
     * @return 到达第n阶的最小成本
     */
    private int dp(int[] cost, int n, int[] memo) {
        // 基本情况：当到达第0阶或第1阶时，不需要支付费用
        if (n == 0 || n == 1) {
            return 0;
        }

        // 如果已经计算过，直接从备忘录中获取结果
        if (memo[n] != -1) {
            return memo[n];
        }

        // 状态转移方程：从n-1阶上来或从n-2阶上来的最小值
        memo[n] = Math.min(dp(cost, n - 1, memo) + cost[n - 1], dp(cost, n - 2, memo) + cost[n - 2]);
        return memo[n]; // 返回计算结果并存入备忘录
    }
}