azl397985856 commented 3 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] 。

yanglr commented 3 years ago

思路:

爬楼梯问题的变形, 应该能用动态规划来做。

方法: 动态规划

题意:

花费相应的体力值后，每次可以跳1步或跳2步。
最后一阶楼梯不需要花费体力值, 因为到了最后一阶不需要再向上跳了。
数据范围 2 <= cost.length <= 1000。

dp数组

dp[i]: 跳到台阶i 的所有方案中的最小代价。

从哪可以只需1次操作就能到达台阶i? 台阶i-2或台阶i-1。

dp[i]只能从dp[i-2]或dp[i-1]变化而来, 取两者最小值。

0 -> … -> i-2 -> i

跳到i的代价是确定的, 即 cost[i]。变化的是从0 -> 台阶i-2的方式, 要使整个代价最小, 需要使从0跳到i-2最小, 经过台阶 i-2跳到台阶 i, 花费的总代价为: dp[i-2] + cost[i]

0 -> … -> i-1 -> i 经过台阶 i-1跳到台阶 i, 花费的总代价为: dp[i-1] + cost[i]

由于最后一阶楼梯不需要花费体力值, 故最后的结果为: dp[n] = min(dp[n-2], dp[n-1]) 故最后的结果为: min(dp[n-2], dp[n-1])

代码

实现语言: C++

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        const int N = cost.size();
        vector<int> dp(N); /* 题意: 2 <= cost.length <= 1000 */
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < N; i++)
            dp[i] = cost[i] + min(dp[i-2], dp[i-1]);
        return min(dp[N-2], dp[N-1]);
    }
};

复杂度分析:

时间复杂度: O(N)，N为原数组cost的长度
空间复杂度: O(N)

Tao-Mao commented 3 years ago

Idea

DP

Code

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int minimumCost[] = new int[cost.length + 1];

        for (int i = 2; i < minimumCost.length; i++) {
            int takeOneStep = minimumCost[i - 1] + cost[i - 1];
            int takeTwoSteps = minimumCost[i - 2] + cost[i - 2];
            minimumCost[i] = Math.min(takeOneStep, takeTwoSteps);
        }

        return minimumCost[minimumCost.length - 1];
    }
}

Complexity

Time O(n) Space O(n)

lilyzhaoyilu commented 3 years ago

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
      int n = cost.size();
      vector<int> 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];
    }
};

florenzliu commented 3 years ago

Explanation

dp
add the top layer in the cost as 0

Python

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

Complexity:

Time Complexity: O(n)
Space Complexity: O(n)

yachtcoder commented 3 years ago

dfs + memo O(n), O(n)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def dfs(i):
            if i >= len(cost):
                return 0
            return min(dfs(i+1), dfs(i+2)) + cost[i]
        return min(dfs(0), dfs(1))

st2yang commented 3 years ago

思路

dp

代码

python

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

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

    return dp[-1]

复杂度

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

JiangyanLiNEU commented 3 years ago

Idea

we start either from index 0 or index 1 and the last location before reach top is either index -1 or index -2
Use a map to memorize what the minimum cost that we can spent at index i
iterate backwards so that we can get the minimum cost at index 0 or 1

Runtime = O(n), Space = O(n)

Python

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

JavaScript

var minCostClimbingStairs = function(cost) {
const length = cost.length;
if (length === 2){
    return Math.min(cost[0], cost[1]);
};
let map = new Map();
map.set(length-1, cost[length-1]);
map.set(length-2, cost[length-2]);

for (let i=length-3; i>=0; i--){
    map.set(i, cost[i]+Math.min(map.get(i+1), map.get(i+2)));
};

return Math.min(map.get(0), map.get(1));
};

yingliucreates commented 3 years ago

link:

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

代码 Javascript

const minCostClimbingStairs = cost => {
  for (let i = 2; i < cost.length; i++) 
    cost[i] = Math.min(cost[i - 1] + cost[i], cost[i - 2] + cost[i]);
  return Math.min(cost.pop(), cost.pop())
};

复杂度分析

time O(n) space O(1)

kidexp commented 3 years ago

thoughts

动态规划

dp[I] 表示跳到i的最小cost

dp[0] = dp[1] = 0

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

结果是 dp[len(costs)]

可以用滚动数组优化

code

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

complexity

Time O(n)

Space O(1)

zhangzz2015 commented 3 years ago

思路

极值问题，可考虑是否可以使用dp。可把该问题抽象如下数学递推关系。定义g(n) 为每一阶楼梯的花费，f(n) 为爬到第n级的最小花费，从n-1最小花费f(n-1)，和n-2最小花费f(n-2)中得到，递推关系为 f(n) = min( f(n-1) + g(n-1), f(n-2)+ g(n-2)) ，有了该递推关系，反向考虑，并定义base情况，f(0) =0 f(1) =0。可依次求解从2 到 n 所有的最小花费。
- 方法1，记录所有2 到 n 的所有花费，时间复杂度为O(n) ，空间复杂度为O(n)。
- 方法2，因为f(n)，仅仅和f(n-1) f(n-2)相关，可压缩只记录前两次，时间复杂度为O(n)，空间复杂度为O(1)。

关键点

代码

语言支持：C++

C++ Code:


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

        //  dp[n] = min(dp[n-1] + cost[n-1], dp[n-2] + cost[n-2] ); 
        int n = cost.size();
        vector<int> dp(n+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];

    }
};

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

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

        return dp[1];

    }
};

thinkfurther commented 3 years ago

思路

用状态转移方程计算下一个状态，同时用两个变量保持前两个状态，减少空间占用

代码

    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0
        pre1 = cost[0]
        pre2 = cost[1]

        for i in range(2, len(cost) + 1):
            current = min(pre1, pre2) + (0 if i == len(cost) else cost[i])
            pre1 = pre2
            pre2 = current

        return current

复杂度

时间复杂度：O(N)

空间复杂度：O(1)

fzzfgbw commented 3 years ago

思路

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

代码

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

复杂度分析

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

leo173701 commented 3 years ago

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

biancaone commented 3 years ago

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

        dp = [0] * len(cost)

        dp[0] = cost[0]
        if len(cost) >= 2:
            dp[1] = cost[1]

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

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

heyqz commented 3 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] = cost[i] + min(dp[i-1], dp[i-2])

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

time complexity: O(n) space complexity: O(n)

mixtureve commented 3 years ago

思路

定义好 dp array 是关键

代码

语言支持：Java

Java Code:


class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // define dp[i]: the min cost to reach i
        // positive costs;
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        // compare: + 1 or + 2
        // start from 0 or start from 1 can end in the same dp[i]
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}
// O(1) space
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int pre2 = 0;
        int pre1 = 0;

        for (int i = 2; i <= cost.length; i++) {
            int temp = pre1;
            pre1 = Math.min(pre1 + cost[i - 1], pre2 + cost[i - 2]);
            pre2 = temp;

        }
        return pre1;
    }
}

复杂度分析

令 n 为数组长度。

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

tongxw commented 3 years ago

思路

dp(i): 到达第i级台阶的最小花费
初始值 dp(0) = 0, dp(1) = 0 因为最多可以走两步
状态转移方程 dp(n) = **min**(dp(n-1) + cost[n-1], dp(n-2) + cost[n-2]) 第n级台阶可以从n-1级台阶跳上来，额外花费cost[n-1]，或从n-2级台阶跳上来，额外花费cost[n-2]。取最小值。

最后别忘了题目要求跳到数组外面一格，就是len(cost)的位置。

代码

class Solution {
public int minCostClimbingStairs(int[] cost) {
    int dp0 = 0;
    int dp1 = 0;
    for (int i=2; i<cost.length + 1; i++) {
        int nextDp = Math.min(dp0 + cost[i - 2], dp1 + cost[i-1]);
        dp0 = dp1;
        dp1 = nextDp;
    }

    return dp1;
}
}

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

pophy commented 3 years ago

思路

动态规划
dp[i] 表示到达 i stair的最小cost
dp[i] = min{dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]} i >= 2

Java Code

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

时间&空间

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

yuxiangdev commented 3 years ago

public int minCostClimbingStairs(int[] cost) {
        // dp[n]: min cost of reaching the n-th step
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], 
                             dp[i - 2] + cost[i - 2]);
        }
        return dp[dp.length - 1];
    }

Time O(n) | Space O(n)

Daniel-Zheng commented 3 years ago

思路

动态规划。

代码(C++)

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

复杂度分析

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

Laurence-try commented 3 years ago

思路

dp

代码

使用语言：Python3

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

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

BlueRui commented 3 years ago

Problem 746. Min Cost Climbing Stairs

Algorithm

This is a simple dynamic programming problem.
Let total[i] be the total minimum total cost to reach the ith step. Then the transfer function is: total[i] = min(total[i-1], total[i-2]) + cost[i].
After getting total array, we return the minimum of the last two values as you can reach the top from the last two steps with no additional cost.

Complexity

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

Code

Language: Java

public int minCostClimbingStairs(int[] cost) {
    // Let total[i] be the min total cost to reach ith step.
    int[] total = new int[cost.length];
    total[0] =  cost[0];
    total[1] =  cost[1];
    for (int i = 2; i < cost.length; i++) {
        total[i] = Math.min(total[i - 1], total[i - 2]) + cost[i];
    }
    return Math.min(total[cost.length - 1], total[cost.length - 2]);
}

zliu1413 commented 3 years ago

class Solution(object): def minCostClimbingStairs(self, cost): """ :type cost: List[int] :rtype: 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: O(n) space: O(n)

MonkofEast commented 3 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)

joeytor commented 3 years ago

思路

dp[i] 代表在第 i 级台阶时的最小 cost

base case dp[0] = 0, dp[1] = 0, 因为可以从 index 0 或者 1 开始

动态转移:

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

对于每一级台阶 i , 都有两种方式可以到达, 从 i-1 用 cost[i-1] 或者从 i-2 用 cost[i-2] 到达, 根据题意, 取两者的最小值作为 dp[i]的数值

return dp[-1] 返回到达最后一级台阶的最小值

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

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

        return dp[-1]

复杂度

时间复杂度: O(n) 遍历一次数组的复杂度

空间复杂度: O(n) dp 数组的空间复杂度, 可以使用滚动数组优化

GZ712D commented 3 years ago

思路

状态转移方程计算next状态，同时两个变量remain前两个状态，reduce空间占用

代码

def minCostClimbingStairs(self, cost: List[int]) -> int:
    if not cost:
        return 1
    pre1 = cost[1]
    pre2 = cost[0]

    for i in range(2, len(cost) + 1):
        current = min(pre1, pre2) + (0 if i == len(cost) else cost[i])
        pre1 = pre2
        pre2 = current

    return current

复杂度

时：O(N) 空：O(1)

freesan44 commented 3 years ago

思路

动态规划，记录动态规划的数组多一位，最后一位把最终值导出来

代码

语言支持：Python3

Python3 Code:


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

if __name__ == '__main__':
    cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    cost = [10, 15, 20]
    res = Solution().minCostClimbingStairs(cost)
    print(res)

复杂度分析

令 n 为数组长度。

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

mannnn6 commented 3 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];
    }
}

复杂度

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

shawncvv commented 3 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]

复杂度

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

ZacheryCao commented 3 years ago

Idea:

Dynamic programming. Transit function: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). dp[i] means the cost to be the ith staircase. To arrive the ith staircase we can start from (i-1)th step with one step at the cost of (i-1)th staircase or (i-2)th with two steps at the cost of (i-2)th staircase

Code:

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

Complexity:

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

yan0327 commented 3 years ago

思路：人生第一道动态规划=-= 感觉还是用递归的思想，用一个n+1位的数组来保存所有的值，初始条件dp[0],dp[1]，然后从i=2 开始遍历，每次判断前两位的最小值再加自己本身。最后求到最后一位，输出即可

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

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

在下面补充一个空间复杂度为1的方法，即滚动数组

func minCostClimbingStairs(cost []int) int {
    if cost == nil || len(cost) == 0{
        return 0
    }
    n := len(cost)
    a := cost[0]
    b := cost[1]
    out := 0
    for i:=2;i<=n;i++{
        if i == n{
            out = min(a,b) + 0
        }else{
            out = min(a,b) + cost[i]
        }
        a = b
        b = out
    }
    return out
}
func min(a,b int) int{
    if a < b{
        return a
    }else{
        return b
    }
}

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

chang-you commented 3 years ago

// class Solution {
//     public int minCostClimbingStairs(int[] cost) {
//         int twoStepBefore = cost[0];
//         int oneStepBefore = cost[1];

//         for (int i = 2; i < cost.length; i++) {
//             int cur = Math.min(twoStepBefore, oneStepBefore) + cost[i];
//             twoStepBefore = oneStepBefore;
//             oneStepBefore = cur;
//         }

//         return Math.min(oneStepBefore, twoStepBefore);
//     }
// }

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

lizzy-123 commented 3 years ago

思路

使用动态规划，dp[i] 代表登上第i个台阶，消耗最小力气。确定dp[i]是因为dp[i-2]和dp[i]得到的代码

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

复杂度分析 时间复杂度：O(N); 空间复杂度:O(N);

suukii commented 3 years ago

Link to LeetCode Problem

S1: 动态规划

将 dp[i] 定义为“走到当前阶梯所需要消耗的最小花费“
根据题意，每次可以选择向上爬一个阶梯或者爬两个阶梯，换句话说，就是可以从第 i-1 或者第 i-2 级台阶走到第 i 级台阶，即 dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
同样的，你可以从第 n-1 或者第 n-2 级台阶走到楼顶，所以最终结果返回 min(dp[n-1], dp[n-2] 即可（楼顶不需要消耗花费）
题目说了，在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯，所以 dp[0] = cost[0], dp[1] = cost[1]

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

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const dp = Array.from({length: n});
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (let i = 2; i < n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    return Math.min(dp[n - 1], dp[n - 2]);
};

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

shixinlovey1314 commented 3 years ago

Title:746. Min Cost Climbing Stairs

Question Reference LeetCode

Solution

Since we will need to pay to cost of a stair if we step on it, we can start from the top of the stairs and go down to the 1st or 2nd stair to find the answer. Start from the top two stairs: if we step on the top stair n, we will have to pay cost[n]: dp[n] = cost[n]; if we step on the second stair from top n-1, we will have to pay cost[n-1]: dp[n-1] = cost[n-1]; if we step on the third stair from the top, we will have to pay cost[n-2] and the minimum cost for n or n -1, so we have dp[n-2] = cost[n-1] + min(dp[n-1], dp[n]);

we go all the way down to the 1 stair, since we could start from eirther 1st or 2nd stair, the answer is min(dp[1st], dp[2nd])

Code

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];

        for (int i = n - 3; i >= 0; i--) {
            dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
        }

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

Complexity

Time Complexity and Explanation

O(n)

Space Complexity and Explanation

O(n)

xj-yan commented 3 years ago

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[1] = cost[0];

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

Time Complexity: O(n), Space Complexity: O(n)

james20141606 commented 3 years ago

Day 54: 746. Min Cost Climbing Stairs (DP)

Problem Link
- 746. Min Cost Climbing Stairs
Ideas
- a classic DP problem, the transition function has two forms: write dp as a whole of dp and cost, or separate cost out. This will affect the initial condition.
Complexity: hash table and bucket
- Time: O(NlogN) #sort algo
- Space: O(N)
Code

#in this case, we treat dp[i-1] + cost[i-1] as a whole!
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]

#in this case, the dp[0] or dp[1] could be used as initial, so it is 0.
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[-1]

other resources:
- https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/

chun1hao commented 3 years ago

var minCostClimbingStairs = function (cost) {
  let len = cost.length;
  let prev = cost[0];
  let cur = cost[1];
  for (let i = 2; i < len; i++) {
    let temp = cur;
    cur = Math.min(cur, prev) + cost[i];
    prev = temp;
  }
  return Math.min(prev, cur);
};

naomiwufzz commented 3 years ago

思路：动态规划

每一节楼梯要么是从前1节上来，要么是从前2节上来

dp[i]表示到楼梯i的最小花费，dp[i]是min(上一节楼梯上来花费，上两节楼梯上来花费)，按照题意，走一步到最后一节不用花费，走两步就需要花费，那么换种理解，走到顶，是把列表里面所有楼梯走完，相当于最后跨上去一步，所以这里加了一个0，这样走一步到最后一节和走两步就一致了。

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 每次只能选爬1或者2
        cost.append(0)
        dp = [0] * (len(cost))
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, len(cost)):
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
        return dp[-1]

复杂度分析

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

Francis-xsc commented 3 years ago

思路

动态规划 dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])

代码


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

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。
空间复杂度：O(N)

EggEggLiu commented 3 years ago

思路

基础动归

代码

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> 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)

wangzehan123 commented 3 years ago

Java Code:


class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int first=0;
        int second=0;
        boolean isFirst=true;
        for(int i=2;i<cost.length+1;i++){
            if(isFirst){
                first=Math.min(first+cost[i-2],second+cost[i-1]);
            }else{
                second=Math.min(first+cost[i-1],second+cost[i-2]);
            }
                isFirst=!isFirst; 
        }
        return isFirst?second:first;
    }
}

复杂度分析

令 n 为数组长度。

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

shamworld commented 3 years ago

思路

动态规划

代码

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

复杂度分析

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

ZhuMengCheng commented 3 years ago

var minCostClimbingStairs = function (cost) {
    let n = cost.length;
    let dp = Array.from({ length: n + 1 }).fill(0)
    dp[0] = dp[1] = 0;
    let first = 0;
    let second = 0;
    // 每1到两位计算最小值
    for (let i = 2; i <= cost.length; i++) {
        const tempFirst = dp[i - 1] + cost[i - 1]
        const tempSecond = dp[i - 2] + cost[i - 2];
        dp[i] = Math.min(tempFirst, tempSecond);
        // const value = Math.min(first + cost[i - 1], second + cost[i - 2]);
        // second = first;
        // first = value;
    }
    return dp[n]
    // return second
};
// 时间复杂度:O(N)
// 空间复杂度:O(N)

hewenyi666 commented 3 years ago

题目名称

746. 使用最小花费爬楼梯

题目链接

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

题目思路

code for Python3

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

复杂度分析

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

muimi commented 3 years ago

思路

动态规划

代码

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

复杂度

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

TimmmYang commented 3 years ago

思路

动态规划。也可以只用三个变量节约空间。

代码

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

复杂度

时间：O(n) n为cost长度。空间：O(n)

ZJP1483469269 commented 3 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] 。

前置知识

公司

暂无

思路

动态规划，类似上楼梯那个问题

关键点

代码

语言支持：Java

Java Code:


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

复杂度分析

令 n 为数组长度。

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

carterrr commented 3 years ago


class 使用最小的花费爬楼梯_746 {
    public int minCostClimbingStairs(int[] cost) {
        // 定义数组 -> 边界值 -> dp递推
        int[] dp = new int[cost.length]; 
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i];
        }
        // 跳上梯顶可以是这两种 ，取最小值即可
        return Math.min(dp[cost.length - 2], dp[cost.length - 1]);
    }
}

Moin-Jer commented 3 years ago

思路

动态规划

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        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];
    }
}

复杂度分析

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

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

【Day 54 】2021-11-02 - 746.使用最小花费爬楼梯 #73

746.使用最小花费爬楼梯

入选理由

题目地址

前置知识

题目描述

思路:

方法: 动态规划

dp数组

代码

复杂度分析:

Idea

Code

Complexity

思路

代码

复杂度

Idea

Python

JavaScript

link:

代码 Javascript

复杂度分析

thoughts

code

complexity

思路

关键点

代码

思路

代码

复杂度

思路

代码

复杂度分析

思路

代码

思路

代码

思路

Java Code

时间&空间

思路

代码(C++)

复杂度分析

思路

代码

Problem 746. Min Cost Climbing Stairs

Algorithm

Complexity

Code

746. Min Cost Climbing Stairs

Algo

Code

Comp

T: O(N)

S: O(N)

思路

复杂度

思路

代码

复杂度

思路

代码

代码

复杂度

思路

代码

Idea:

Code:

Complexity:

S1: 动态规划

Title:746. Min Cost Climbing Stairs

Question Reference LeetCode

Solution

Code

Complexity

Time Complexity and Explanation

Space Complexity and Explanation