大家好,我是晴天学长,很重要的思想动规思想,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪
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]);
}
}
5).总结
- 状态转移思想。
试题链接: