题目描述
数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。
每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1:
输入:cost = [10, 15, 20]
输出:15
解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。
示例 2:
输入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出:6
解释:最低花费方式是从 cost[0] 开始,逐个经过那些 1 ,跳过 cost[3] ,一共花费 6 。
提示:
cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据,范围为 [0, 999] 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
动态规划:
题目理解:
- 你可以花费cost[i]的体力值,向上跳一个台阶或者两个台阶;
- 你可以选择台阶起点为cost[o]或者cost[1]
- 使用最少体力值,跳出数组边界即为成功;
举例1: 如果从cost[0]作为台阶起点,跳出数组的方案有:
- 向前跳一个台阶,再跳两个台阶,此时跳出数组:
- 消耗体力:cost[0]+cost[1]=10+15=25;
- 向前跳两个台阶,再跳一个台阶,此时跳出数组:
- 消耗体力:cost[0]+cost[2]=10+20=30;
如果从cost[1]作为台阶起点,跳出数组的方案有:
- 向前跳两个台阶,此时跳出数组
- 消耗体力:cost[1]=15;
因此最优解为:15; 举例2: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 选择cost[0]作为台阶起点,跳出数组的方案有:
- 向前跳两个台阶到cost[2],再向前跳两个台阶到cost[4],
再向前跳两个台阶到cost[6],再向前跳一个台阶到cost[7], 再向前跳两个台阶到cost[9],最后跳出最后一个台阶跳出数组;
- 消耗体力:
- cost[0]+cost[2]+cost[4]+cost[6]+cost[7]+cost[9]=1+1+1+1+1+1=6
标准动态规划问题:
- dp[i]表示爬到第i阶台阶时,消耗的最小体力值;
- 到达dp[i]台阶有两种方法;
- dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
- dp[0]=0;dp[1]=0;dp[2]=min(dp[1]+cost[1],dp[0]+cost[0]);
代码
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
let n=cost.length; // 台阶数;
const dp=new Array(n+1); // n+1到楼顶的长度数组;
dp[0]=dp[1]=0;
for(let i=2;i<=n;i++){
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
};
解题思路
双指针-滚动数组思想
- 定义指针prev,curr;
- next=Math.min(curr+cost[i-1],prev+cost[i-2]);
- next 指向向上跳台阶的最小体力消耗值;
- 指针prev指向上一步,curr指向当前台阶:
- prev=curr;curr=next;
代码
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function(cost) {
let n=cost.length; // 台阶数;
let prev=0,curr=0;
for(let i=2;i<=n;i++){
let next=Math.min(curr+cost[i-1],prev+cost[i-2]);
prev=curr;
curr=next;
}
return curr
};
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!