字节&leetcode746：使用最小花费爬楼梯 #91

Activity

1. sisterAn

   added

   LeetCode

   字节

   on Jul 29, 2020
2. sisterAn commented on Jul 29, 2020

   

   sisterAn

   on Jul 29, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法：动态规划

   本题注意理解题意：

   • 第 i 级台阶是第 i-1 级台阶的阶梯顶部。
   • 踏上第 i 级台阶花费 cost[i] ，直接迈一大步跨过而不踏上去则不用花费。
   • 楼梯顶部在数组之外，如果数组长度为 len，那么楼顶就在下标为 len

   第一步：定义子问题

   踏上第 i 级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：

   • 最后迈 1 步踏上第 i 级台阶：dp[i-1] + cost[i]
   • 最后迈 2 步踏上第 i 级台阶：dp[i-2] + cost[i]

   第二步：实现需要反复执行解决的子子问题部分

   所以踏上第 i 级台阶的最小花费为：

   dp[i] = min(dp[i-2], dp[i-1]) + cost[i]

   第三步：识别并求解出边界条件

   // 第 0 级 cost[0] 种方案 
   dp[0] = cost[0]
   // 第 1 级，有两种情况
   // 1：分别踏上第0级与第1级台阶，花费cost[0] + cost[1]
   // 2：直接从地面开始迈两步直接踏上第1级台阶，花费cost[1]
   dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]

   最后一步：把尾码翻译成代码，处理一些边界情况

   let minCostClimbingStairs = function(cost) {
       cost.push(0)
       let dp = [], n = cost.length
       dp[0] = cost[0]
       dp[1] = cost[1]
       for(let i = 2; i < n; i++){
           dp[i] = Math.min(dp[i-2] , dp[i-1]) + cost[i]
       }
       return dp[n-1]
   }

   复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

   优化：

   let minCostClimbingStairs = function(cost) {
       let n = cost.length,
           n1 = cost[0],
           n2 = cost[1] 
       for(let i = 2;i < n;i++){
           let tmp = n2
           n2 = Math.min(n1,n2)+cost[i]
           n1 = tmp
       }
       return Math.min(n1,n2)
   };

   • 时间复杂度：O(n)
   • 空间复杂度：O(1)

   leetcode

   👍React with 👍1Reacted by demo
3. ruofee commented on Mar 10, 2021

   

   ruofee

   on Mar 10, 2021

   More actions

   最后迈 1 步踏上第 i 级台阶：dp[i-1] + cost[i]
   最后迈 1 步踏上第 i 级台阶：dp[i-2] + cost[i]

   这里说错了, 应该是: 最后迈 2 步踏上第 i 级台阶：dp[i-2] + cost[i]

   😄React with 😄1Reacted by Stephan_zhang