LeetCode算法心得——使用最小花费爬楼梯（记忆化搜索+dp）

大家好，我是晴天学长，很重要的思想动规思想，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

---

1）使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

2 <= cost.length <= 1000
0 <= cost[i] <= 999

---

2) .算法思路

• 有点像变了的样子的打家劫舍，可以打劫附近的房子了。

---

3) .算法步骤

定义一个整型数组 memo 和 cost，用于存储记忆化搜索的结果和每个楼梯的代价。
创建 minCostClimbingStairs 方法来启动算法。在该方法中，初始化 memo 数组和 cost 数组，并将 memo 数组的所有元素初始化为 -1。
调用 dfs 方法，将起始索引设为 cost.length - 1（最后一个楼梯），并返回从最后一个楼梯开始上楼梯的最小代价。
在 dfs 方法中，首先检查是否已经搜索过当前索引 i 的结果。如果在 memo 数组中存在已计算的值，则直接返回该值作为结果，避免重复计算。
如果当前索引 i 小于 0，表示已经超出楼梯范围，返回 0。
否则，根据动态规划的思想，当前楼梯 i 的最小代价等于从前一个楼梯 i-1 或者前两个楼梯 i-2 上来的最小代价加上当前楼梯的代价。使用递归调用 dfs 方法，分别计算从 i-1 楼梯和 i-2 楼梯上来的最小代价，并将它们与当前楼梯的代价相加并取最小值。
将计算得到的结果存储在 memo 数组中，以备后续使用。
返回当前索引 i 的结果作为最终答案，即从最后一个楼梯出发的最小代价。

---

4）.代码示例

方法1：记忆化搜索。
 class Solution {
        int[] memo;
        int[] cost;

        public int minCostClimbingStairs(int[] cost) {
            memo = new int[1000];
            this.cost = cost;
            Arrays.fill(memo, -1);
            return Math.min(dfs(cost.length - 1), dfs(cost.length - 2));
        }

        //变相的打家劫舍, 到楼梯发现已经爬上来了，不能选择不爬
        private int dfs(int i) {
            if (i < 0) return 0;
            if (memo[i] != -1) return memo[i];
            int result = Math.min(dfs(i - 1) + cost[i], dfs(i - 2) + cost[i]);
            memo[i] = result;
            return result;
        }
    }
方法2：动态规划dp
//感兴趣的小伙伴可以用一个数组来打表，优化空间复杂度。
 class Solution {
        public int minCostClimbingStairs(int[] cost) {
            int[] dp = new int[cost.length];
            dp[0] = cost[0];
            dp[1] = cost[1];
            for (int i = 2; i < dp.length; i++) {
                dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i]);
            }
            return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

5）.总结

• 状态转移思想。

---

试题链接：