【魅力算法】“使用最小花费爬楼梯”-动态规划、双指针-滚动数组思想实现 |刷题打卡

作者: 稀土掘金  更新时间:2021-03-09 10:44:58  原文链接


【魅力算法】“使用最小花费爬楼梯”-动态规划、双指针-滚动数组思想实现 |刷题打卡

题目描述

数组的每个下标作为一个阶梯,第 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]);

时间复杂度O(n); 空间复杂度O(1)

代码

/**
 * @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;

时间复杂度O(n) ;空间复杂度O(1)

代码

/**
 * @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
};