azl397985856 commented 2 years ago

746.使用最小花费爬楼梯

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

前置知识

动态规划

题目描述


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

wenlong201807 commented 2 years ago

代码块


var minCostClimbingStairs = function (cost) {
  const dp = [cost[0], cost[1]];

  for (let i = 2; i < cost.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]);
};

时间复杂度和空间复杂度

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

Richard-LYF commented 2 years ago

class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int:

    a= b= 0

    for i in range(2,len(cost) + 1):
        c = min(a + cost[i-2],b + cost[i-1])
        a=b
        b=c

    return c

    # on o1

yetfan commented 2 years ago

思路 dp逆推，从倒数第三个位置 "最小cost" = “自身”+"其后两个位置的最小值"

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(3, len(cost)+1):
            cost[-i] += min(cost[-i+1], cost[-i+2]) 
        return min(cost[0], cost[1])

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

Alfie100 commented 2 years ago

题目链接： 746. 使用最小花费爬楼梯 https://leetcode-cn.com/problems/min-cost-climbing-stairs/

解题思路

动态规划 + 状态压缩。

Python 代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:

        n = len(cost)
        # dp = [0] * (n+1)

        x, y = 0, 0
        for i in range(2, n+1):
            # dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
            x, y = y, min(y+cost[i-1], x+cost[i-2])

        return y

复杂度分析

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

ZJP1483469269 commented 2 years ago

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)
        for i in range(2,n + 1):
            dp[i] = min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2])

        return dp[n]

charlestang commented 2 years ago

思路

动态规划 f(i) = min(f(i -1) + cost(i-1), f(i - 2) + cost(i -2))，时间复杂度 O(n)

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        a = 0
        b = 0
        c = 0
        for i in range(2, n + 1):
            c = min(a + cost[i - 1], b + cost[i - 2])
            b = a
            a = c
        return c

yijing-wu commented 2 years ago

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

laofuWF commented 2 years ago

# use dp[i] to track min cost to get to i and make the move
# dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
# final res is min(dp[-1], dp[-2]), since we can reach top from both the last or the second to last

# time: O(N)
# space: O(N)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:        
        dp = [1000 for i in range(len(cost))]
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

        return min(dp[-1], dp[-2])

# space improved version
# time: O(N)
# space: O(1)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:        
        prev1 = cost[0]
        prev2 = cost[1]

        for i in range(2, len(cost)):
            curr = min(prev1, prev2) + cost[i]
            prev1 = prev2
            prev2 = curr

        return min(prev1, prev2)

moirobinzhang commented 2 years ago

Code:

public int MinCostClimbingStairs(int[] cost) {
    if (cost == null || cost.Length == 0)
        return 0;

    int[] dp = new int[cost.Length + 1];
    dp[0] = cost[0];
    dp[1] = cost[1];

    for (int i = 2; i <= cost.Length; i++)
        dp[i] = Math.Min(dp[i - 1], dp[i - 2]) + ( i == cost.Length ? 0 : cost[i]);

    return dp[cost.Length];        
}

LannyX commented 2 years ago

思路

DP

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length - 1;
        int[] dp = new int[cost.length];
        dp[0] = 0; //Math.min(cost[-1], cost[0])
        dp[1] = Math.min(cost[0], cost[1]);

        for(int i = 2; i <= n; i++){
            dp[i] =  Math.min(dp[i - 2] + cost[i - 1], dp[i - 1] + cost[i]);
        }
        return dp[n];
    }
}

复杂度分析

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

RocJeMaintiendrai commented 2 years ago

class Solution { public int minCostClimbingStairs(int[] cost) { int f1 = 0; int f2 = 0; for(int i = cost.length - 1; i >= 0; i--) { int f0 = cost[i] + Math.min(f1, f2); f2 = f1; f1 = f0; } return Math.min(f1, f2); } }

ZacheryCao commented 2 years ago

Idea

Dynamic Programming

Code

#include<cmath>
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        for(int i = 2; i < cost.size(); i++){
            cost[i] = min(cost[i-1], cost[i-2]) + cost[i];
        }
        return min(cost[cost.size()-1], cost[cost.size()-2]);
    }
};

Complexity:

Time: O(N) Space: O(1)

mannnn6 commented 2 years ago

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

CoreJa commented 2 years ago

思路

DFS：回溯大法，TLE
DFS+记忆化：好用，本质和动规一样。复杂度$O(n)$
动规：过！复杂度$O(n)$

代码

class Solution:
    def minCostClimbingStairs1(self, cost: List[int]) -> int:
        def dfs(i):
            if i < 2:
                return cost[i]
            return cost[i] + min(dfs(i - 1), dfs(i - 2))

        n = len(cost)
        return min(dfs(n - 2), dfs(n - 1))

    def minCostClimbingStairs2(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [cost[0], cost[1]] + [-1] * (n - 2)

        def dfs(i):
            if dp[i] != -1:
                return dp[i]
            dp[i] = cost[i] + min(dfs(i - 1), dfs(i - 2))
            return dp[i]

        return min(dfs(n - 2), dfs(n - 1))

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [cost[0], cost[1]] + [0] * (n - 2)
        for i in range(2, n):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
        return min(dp[-1], dp[-2])

xinhaoyi commented 2 years ago

746. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。

请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

思路一

这一题的核心是每一步都有越级和不越级的两种选择，然后要达到最后总体力值消耗最少的结果，很容易联想到使用动态规划，列出状态转移方程即可。

这题题意要审清，选择 cost[0] 作为初始阶梯，是指我人还在地面上，要付出cost[0]的体力值，才能到0号阶梯顶部，也就是登上0号阶梯

选择cost[1]作为初始阶梯，是指我人就踩在0号阶梯上，也就是在0号阶梯的顶部，要再付出cost[1]的体力值才能登上1号阶梯

要登上i号阶梯，怎么花最少的体力呢？

有两种情况，第一种是先花最少的体力登上i - 1号阶梯，再花cost[i]登上i号阶梯 minTotalCost[i - 1] + cost[i]

第二种是想花最少体力登上 i - 2 号阶梯，再花 cost[i - 1] 的体力越级直接登上i号阶梯 minTotalCost[ i - 2] + cost[i - 1]

minTotalCost[i] 指登上i号阶梯一共需要的最少体力值，取上述两种情况中更小的一个

minTotalCost[i] = min{minTotalCost[i - 1] + cost[i] , minTotalCost[ i - 2] + cost[i - 1]}

我们再找出minTotalCost[0]和minTotalCost[1]的值，然后就可以从2开始不断往后递推

minTotalCost[0] ，即登上 0 号台阶需要花的最少总体力值，要么从地面出发付出cost[0]，要么直接站在0号台阶顶部，花费0

所以minTotalCost[0] = min{cost[0] , 0} = 0

minTotalCost[1] 要么从地面出发，付出cost[0]后越级直接登上1号台阶，要么从0号台阶(顶部)出发，付出cost[1]后直接到达1号台阶

所以minTotalCost[1] = min{cost[1] , cost[2]}

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        /**
        这一题的核心是每一步都有越级和不越级的两种选择，然后要达到最后总体力值消耗最少的结果，很容易联想到使用动态规划，列出状态转移方程即可。
        这题题意要审清，选择 cost[0] 作为初始阶梯，是指我人还在地面上，要付出cost[0]的体力值，才能到0号阶梯顶部，也就是登上0号阶梯
        选择cost[1]作为初始阶梯，是指我人就踩在0号阶梯上，也就是在0号阶梯的顶部，要再付出cost[1]的体力值才能登上1号阶梯
        要登上i号阶梯，怎么花最少的体力呢？
        有两种情况，第一种是先花最少的体力登上i - 1号阶梯，再花cost[i]登上i号阶梯 minTotalCost[i - 1] + cost[i]
        第二种是想花最少体力登上 i - 2 号阶梯，再花 cost[i - 1] 的体力越级直接登上i号阶梯 minTotalCost[i - 2] + cost[i - 1]
        minTotalCost[i] 指登上i号阶梯一共需要的最少体力值，取上述两种情况中更小的一个
        minTotalCost[i] = min{minTotalCost[i - 1] + cost[i] , minTotalCost[ i - 2] + cost[i - 1]}
        我们再找出minTotalCost[0]和minTotalCost[1]的值，然后就可以从2开始不断往后递推
        minTotalCost[0] ，即登上 0 号台阶需要花的最少总体力值，要么从地面出发 付出cost[0]，要么直接站在0号台阶顶部，花费0
        所以minTotalCost[0]  = min{cost[0] , 0} = 0
        minTotalCost[1] 要么从地面出发，付出cost[0]后越级直接登上1号台阶，要么从0号台阶(顶部)出发，付出cost[1]后直接到达1号台阶
        所以minTotalCost[1] = min{cost[1] , cost[2]}
         */

        //解法一
        //楼梯个数
         int size = cost.length;
         //创建最小总花费数组
         int[] minTotalCost = new int[size];
         minTotalCost[0] = 0;
         minTotalCost[1] = Math.min(cost[0],cost[1]);//题目说了cost 的长度范围是 [2, 1000]
         for(int i = 2; i < size; i++){
             minTotalCost[i] = Math.min(minTotalCost[i-1] + cost[i] , minTotalCost[i-2] + cost[i-1]);
         }
         return minTotalCost[size - 1];

    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

思路二

在思路一的基础上优化代码，我们目前借助了一个辅助数组minTotalCost[] ，空间复杂度为O(n)，这个可以优化

注意到状态转移方程的每一步都只涉及三个变量，我们可以去掉数组，只维护这三个变量，并不断更新，效果是一样的

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //解法二
        //在解法一的基础上优化代码

        //楼梯个数
        int size = cost.length;

        int minTotalCost0 = 0; //minTotalCost[0] = 0;
        int minTotalCost1 = Math.min(cost[0],cost[1]); //minTotalCost[1] = Math.min(cost[0],cost[1])

        //需要的答案
        //debug: 注意这里不能写成minTotalCost2 = 0，初值一定要和minTotalCost1相等
        //否则，如果就只有两个楼梯，底下的for循环是直接跳过的，那么你的最小总花费岂不是0了，这就不行
        int minTotalCost2 = minTotalCost1;

        for(int i = 2; i < size; i++){
            minTotalCost2 = Math.min(minTotalCost1 + cost[i] , minTotalCost0 + cost[i-1]);
            minTotalCost0 = minTotalCost1;
            minTotalCost1 = minTotalCost2;
        }
        return minTotalCost2;
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

LinnSky commented 2 years ago

思路

动态规划

代码

     var minCostClimbingStairs = function(cost) {
        const dp = [cost[0], cost[1]]
        for(let i = 2; i < cost.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])
    };

复杂度分析

时间复杂度O(N)
空间复杂度O(N)

Tesla-1i commented 2 years ago

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length - 1;
        int[] dp = new int[cost.length];
        dp[0] = 0; //Math.min(cost[-1], cost[0])
        dp[1] = Math.min(cost[0], cost[1]);

        for(int i = 2; i <= n; i++){
            dp[i] =  Math.min(dp[i - 2] + cost[i - 1], dp[i - 1] + cost[i]);
        }
        return dp[n];
    }
}

Aobasyp commented 2 years ago

思路动态规划

class Solution { public: int minCostClimbingStairs(vector& cost) { int n = cost.size(); vector dp(n + 1); dp[0] = dp[1] = 0; for(int i = 2; i <= n; i++){ dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); }

  return dp[n];
}

};

时间复杂度：O(N) 空间复杂度：O(N)

xuhzyy commented 2 years ago

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        n = len(cost)
        dp = [0] * n
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2, n):
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        return min(dp[n-1], dp[n-2])

watchpoints commented 2 years ago

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

      int n =cost.size();

      int curstepSum =0;//走过阶梯i消耗的能量
      int preStepSum =0;//走过阶梯i-1,消耗的能量

      for(int i=0;i <= n;i++)
      {
        int cur =min(curstepSum,preStepSum) + (i == n ? 0 : cost[i]);
        //楼顶不需要消耗能量

         preStepSum =curstepSum;
         curstepSum =cur;
      }
      return curstepSum;
    }
};

haixiaolu commented 2 years ago

思路

动态规划，倒序

代码/python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cost.append(0)
        # reverse order
        for i in range(len(cost) - 3, -1, -1):  # we want to reach the third positon backwards
            cost[i] = min(cost[i] + cost[i + 1], cost[i] + cost[i + 2])

        return min(cost[0], cost[1])

复杂度分析

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

Myleswork commented 2 years ago

思路

DP，动态变量优化空间

代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) { 
        int former = 0;
        int later = 0;
        for(int i = 2;i<=cost.size();i++){
            int tmp = later;
            later = min(former+cost[i-2],later+cost[i-1]);
            former = tmp;
        }
        return later;
    }
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

zhangzz2015 commented 2 years ago

思路

先考虑Top down dfs + mem方法，再思考bottom up dp方法，dp[i] = min(cost[i] + dp[i+1] , cost[i] + dp[i+2]) ，进一步可压缩内存到O(1)，时间复杂度位O(n)，空间复杂度位O(1)

关键点

代码

语言支持：C++

C++ Code:


class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
       //  Time O(n) Space O(n)  Use 10min. 
      int n = cost.size(); 
      int preprev = 0; 
      int prev = cost[n-1]; 
      for(int i=n-2; i>=0; i--)
      {
          int current = min(cost[i]+prev, cost[i]+preprev); 
          preprev = prev; 
          prev = current;           
      }

      return min(prev, preprev);       

    }

    int dpMethod1(vector<int>& cost)
    {
      vector<int> dp(cost.size()+1, 0); 
      // dp[i] =  min(cost[i]+dp[i+1], cost[i]+dp[i+2]);
      for(int i= cost.size()-1; i>=0; i--)
      {
          if(i== cost.size()-1)
              dp[i] =cost[i]; 
          else
              dp[i] = min(cost[i]+dp[i+1], cost[i]+dp[i+2]); 
      }

      return min(dp[0], dp[1]);       
    }

    int dfsMethodMem(vector<int>& cost)
    {
       vector<int> mem(cost.size(), -1);  
       return min(dfs(cost, 0, mem), dfs(cost,1, mem));         
    }    
    int dfs(vector<int>& cost, int start, vector<int>& mem)
    {
        if(start>=cost.size())
            return 0; 
        if(mem[start]!=-1) return mem[start]; 

        mem[start] = min(dfs(cost, start+1, mem)+cost[start], 
                         dfs(cost, start+2, mem)+cost[start]);                 
        return mem[start]; 
    }            
};

cszys888 commented 2 years ago

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0]*n
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2,n):
            dp[i] = min(dp[i - 2] + cost[i],dp[i - 1] + cost[i])
        return min(dp[n-1], dp[n-2])

time complexity: O(N) space complexity: O(N)

zjsuper commented 2 years ago

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) == 0:
            return
        if len(cost) == 1:
            return cost[0]
        co = [0]*(len(cost))   
        co[0] = cost[0]
        co[1] = cost[1]
        #print(co)
        for i in range(2,len(cost)):
            #print(co[i-1],co[i-2]+cost[i])
            co[i] = min(co[i-1],co[i-2])+cost[i]
            #print(co)
        return min(co[-1],co[-2])

z1ggy-o commented 2 years ago

思路

题目要求最值，联想到可能需要使用 DP。

题目分析后，可以转变为，到达当前层数的最小耗费 = min（到前一层的最小耗费+前一层的耗费，到前两层的最小耗费+前两层的耗费）。

可以看出，当前解是由之前解得来，使用 DP 是对的。

代码

因为只需要最后的答案，为了减少空间耗费，没有存储所有的层数的消耗。

CPP

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();

        int one_prev = 0, two_prev = 0;
        int curr = 0;
        for (int i = 2; i <= n; i++) {
            curr = min(one_prev + cost[i-1], two_prev + cost[i-2]);
            // update
            two_prev = one_prev;
            one_prev = curr; 
        }
        return one_prev;
    }
};

复杂度分析

时间：O(n), n is the length of the array
空间：O(1)

MonkofEast commented 2 years ago

746. Min Cost Climbing Stairs

Click Me

Algo

Code

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # recursion equation: dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        # boundary: i == 0 or i == 1
        dp = [cost[0], cost[1]]
        for i in range(2, len(cost)): dp.append(min(dp[i-1], dp[i-2]) + cost[i])
        return min(dp[-1], dp[-2])

Comp

T: O(N)

S: O(N)

feifan-bai commented 2 years ago

思路

DP

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost)+1)
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, len(cost)+1):
            dp[i] = min(dp[i-1], dp[i-2]) + (cost[i] if i != len(cost) else 0)
        return dp[-1]

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

zhangzhengNeu commented 2 years ago

CPP

class Solution { public: int minCostClimbingStairs(vector& cost) { int n = cost.size();

    int one_prev = 0, two_prev = 0;
    int curr = 0;
    for (int i = 2; i <= n; i++) {
        curr = min(one_prev + cost[i-1], two_prev + cost[i-2]);
        // update
        two_prev = one_prev;
        one_prev = curr; 
    }
    return one_prev;
}

};

honeymeng-hub commented 2 years ago

class Solution { public: int minCostClimbingStairs(vector& cost) { int n = cost.size();

    int one_prev = 0, two_prev = 0;
    int curr = 0;
    for (int i = 2; i <= n; i++) {
        curr = min(one_prev + cost[i-1], two_prev + cost[i-2]);
        // update
        two_prev = one_prev;
        one_prev = curr; 
    }
    return one_prev;
}

};

vuesch commented 2 years ago

代码


var minCostClimbingStairs = function (cost) {
  const dp = [cost[0], cost[1]];

  for (let i = 2; i < cost.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]);
};

复杂度分析

时间：O(n), n is the length of the array
空间：O(1)

iambigchen commented 2 years ago

思路

动态规划，定义dp，dp[i]代表着第i步需要的最低消耗，因为可以走一到两步，所以dp[i]= Math.min(dp[i - 1], dp[i - 2]) + cost[i]；我们需要前两步的值即dp[0]和dp[1]

关键点

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
  const dp = [cost[0], cost[1]];

  for (let i = 2; i < cost.length; ++i) {
    dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
  }

  return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
};

复杂度分析

令 n 为数组长度。

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

hdyhdy commented 2 years ago

思路：动态规划

func minCostClimbingStairs(cost []int) int {
    lens := len(cost)
    ans := make([]int,lens + 1)
    for i := 2; i <= lens;i ++ {
            ans[i] = min(ans[i - 1] + cost[i - 1],ans[i - 2] + cost[i - 2])
    }
    return ans[lens]
}

func min(i,j int) int {
    if i > j {
        return j
    }else {
        return i 
    }
}

时间复杂度：O（n）空间复杂度：O（n）

ryan0218 commented 2 years ago

class Solution {

public int minCostClimbingStairs(int[] cost) {

    int n = cost.length;

    int prev = 0, curr = 0;

    for (int i = 2; i <= n; i++) {

        int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);

        prev = curr;

        curr = next;

    }

    return curr;

}

}

zol013 commented 2 years ago

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, len(cost) + 1):
            dp[i] = min(dp[i - 1], dp[i - 2]) + (cost[i] if i < len(cost) else 0)

        return dp[-1]

alongchong commented 2 years ago

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

jiaqiliu37 commented 2 years ago

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0]*len(cost)
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, len(cost)):
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

        return min(dp[-1], dp[-2])

Time complexity O(n) Space complexity O(n)

tongxw commented 2 years ago

思路

dp(i) = min(cost[i-1] + dp(i-1), cost[i-2] + dp(i-2)) 用滚动数组优化空间

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // dp(i) = min(cost[i-1] + dp(i-1), cost[i-2] + dp(i-2))
        int[] dp = new int[3];
        for (int i=2; i<=cost.length; i++) {
            dp[i%3] = Math.min(cost[i-1] + dp[(i-1)%3], cost[i-2] + dp[(i-2)%3]);
        }

        return dp[cost.length % 3];
    }
}

TC: O(n) SC: O(1)

falconruo commented 2 years ago

思路:

动态规划

复杂度分析:

时间复杂度: O(N), 其中N是数组cost的长度
空间复杂度: O(1)

代码:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int pre = 0, cur = 0;

        for (int i = 2; i <= cost.size(); i++) {
            int nxt = min(pre + cost[i - 2], cur + cost[i - 1]);
            pre = cur;
            cur = nxt;
        }

        return cur;
    }
};

xianxianxianyu commented 2 years ago

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int len = cost.size(), a[len + 10];

        a[0] = cost[0];
        a[1] = cost[1];

        for(int i = 2; i < len; i ++)
            a[i] = min(a[i - 1], a[i - 2]) + cost[i];

        return min(a[len - 1], a[len - 2]);
    }
};

anyingbinglong commented 2 years ago

思路:

动态规划

复杂度分析:

时间复杂度: O(N), 其中N是数组cost的长度空间复杂度: O(1) 代码:

class Solution { public: int minCostClimbingStairs(vector& cost) { int pre = 0, cur = 0;

    for (int i = 2; i <= cost.size(); i++) {
        int nxt = min(pre + cost[i - 2], cur + cost[i - 1]);
        pre = cur;
        cur = nxt;
    }

    return cur;
}

};

yan0327 commented 2 years ago


func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int,n+1)
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i:=2;i<len(dp);i++{
        if i <len(cost){
            dp[i] = min(dp[i-1],dp[i-2]) +cost[i]
        }else {
            dp[i] = min(dp[i-1],dp[i-2])
        }
    }
    return dp[n]

}
func min(a,b int) int{
    if a < b{
        return a
    }
        return b
}

Serena9 commented 2 years ago

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost)+1)
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, len(cost)+1):
            dp[i] = min(dp[i-1], dp[i-2]) + (cost[i] if i != len(cost) else 0)
        return dp[-1]

declan92 commented 2 years ago

思路
dp(n)表示爬到第n个台阶的最小花费;(状态定义)
dp(n) = Math.min(dp(n-1)+cost[n-1],dp(n-2)+cost[n-2]);(状态转移方程)
dp(0) = 0,dp(1) = 0;(边界)
从小到大遍历;(枚举);
java code

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int m=0,n=0;
        for(int i=2;i<cost.length+1;i++){
            temp = Math.min(m+cost[i-1],n+cost[i-2]);
            n = m;
            m = temp;
        }
        return m;
    }
}

时间:O(n),n为cost数组长度,也是状态数;
空间:O(1),滚动数组优化;

JudyZhou95 commented 2 years ago

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)

        if n < 3:
            return min(cost)

        prev_prev = cost[0]
        prev = cost[1]

        for i in range(2, n):
            cur = min(prev_prev, prev) + cost[i]
            prev_prev = prev
            prev = cur

        return min(prev_prev, prev)

复杂度

TC: O(N) SC: O(1)

Toms-BigData commented 2 years ago

【Day 54】746.使用最小花费爬楼梯

思路

动态规划

golang代码

func minCostClimbingStairs(cost []int) int {
    dp:=make([]int, len(cost)+1)
    dp[0], dp[1] = cost[0], cost[1]
    min:=func(a, b int) int {
        if a>b{
            return b
        }
        return a
    }

    for i := 2; i < len(cost)+1; i++ {
        dp[i] = min(dp[i-1], dp[i-2])
        if i!=len(cost){
            dp[i] += cost[i]
        }
    }
    return dp[len(dp)-1]
}

复杂度

时间:O(n) 空间:O(n)

1149004121 commented 2 years ago

使用最小花费爬楼梯

思路

动态规划。

代码

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

复杂度分析

时间复杂度：O(N)。
空间复杂度：O(N)。

biaohuazhou commented 2 years ago

思路

动态规划

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }

复杂度分析 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

stackvoid commented 2 years ago

思路

动态规划简单题

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int size = cost.length;
        int[] minCost = new int[size];
        minCost[0] = 0;
        minCost[1] = Math.min(cost[0], cost[1]);
        for (int i = 2; i < size; i++) {
            minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);
        }
        return minCost[size - 1];
    }
}

复杂度分析

Time O(N) Space O(N)

CodingProgrammer commented 2 years ago

思路

DP，斐波那契数列变形，初始化第 0 个位置和第 1 个位置的花费均为0，后续一直保持跳到当前位置的花费最小即可

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost == null || cost.length < 2) {
            throw new IllegalArgumentException();
        }
        int length = cost.length;
        // dp[i] 表示爬到第 i 阶台阶的最少花费
        int[] dp = new int[length + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[length];
    }
}

复杂度

Time: O(N)
Space: O(N)

使用常量代替数组，额外空间复杂度降到 O(1)

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost == null || cost.length < 2) {
            throw new IllegalArgumentException();
        }
        int length = cost.length;
        // dp[i] 表示爬到第 i 阶台阶的最少花费
        int step1 = 0, step2 = 0;
        int res = Integer.MAX_VALUE;
        for (int i = 2; i <= length; i++) {
            res = Math.min(step1 + cost[i - 1], step2 + cost[i - 2]);
            step2 = step1;
            step1 = res;
        }
        return res;
    }
}

leetcode-pp / 91alg-6-daily-check

【Day 54 】2022-02-03 - 746.使用最小花费爬楼梯 #64

746.使用最小花费爬楼梯

入选理由

题目地址

前置知识

题目描述

代码块

时间复杂度和空间复杂度

解题思路

Python 代码

思路

代码

思路

代码

Idea

Code

Complexity:

思路

代码

746. 使用最小花费爬楼梯

思路一

代码

复杂度分析

思路二

代码

复杂度分析

思路

代码

复杂度分析

思路

代码/python

复杂度分析

思路

代码

思路

关键点

代码

思路

代码

746. Min Cost Climbing Stairs

Algo

Code

Comp

T: O(N)

S: O(N)

代码

复杂度分析

思路

关键点

代码

思路

代码

代码

复杂度

【Day 54】746.使用最小花费爬楼梯

思路

golang代码

复杂度

思路

代码

思路

代码

复杂度分析

思路

代码

复杂度

使用常量代替数组，额外空间复杂度降到 O(1)