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] 。

HuiWang1020 commented 2 years ago

Idea

Bottom up DP

Code

public int minCostClimbingStairs(int[] cost) {   
        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]) + cost[i];
        }
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }

Complexity

time=o(time) space=o(n)

ghost commented 2 years ago

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

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

        return dp[-1]

zhiyuanpeng commented 2 years ago

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

time O(N) space O(N)

zqwwei commented 2 years ago

Code

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

        return minCost[minCost.length - 1];
    }

JiangWenqi commented 2 years ago

C++

Solution 1

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

Solution 2

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

MichaelXi3 commented 2 years ago

Idea

Store the past results to DP_Array to avoid repetitive computation

We can think from either TopDown_Dp or BottomUP_DP perspectives

Code

TopDown_DP

class Solution {

int[] dp; // DP array records the minCost of climbing to each stair

public int minCostClimbingStairs(int[] cost) {
    int numberOfStairs = cost.length;
    dp = new int[numberOfStairs]; 

    // To finish climbing stairs, you can either climb to the step at very end or end - 1
    return Math.min(climb(cost, numberOfStairs - 1), climb(cost, numberOfStairs - 2));
}

private int climb(int[] cost, int numberOfStairs) {
    // topToBottom Logic
    int curStep = numberOfStairs;

    // Base cases: If we reach bottom, return initial cost
    if (curStep == 0 || curStep == 1) {
        return cost[curStep];
    }

    // Avoid repetitive memorize 
    if (dp[curStep] != 0) {
        return dp[curStep];
    }

    // DP: Memoization
    dp[curStep] = Math.min(climb(cost, curStep - 1), climb(cost, curStep - 2)) + cost[curStep];   

    // Result: minCost of climb cost.length steps
    return dp[numberOfStairs];
}
}

Complexity

Time O(N) → to find all dp array values, n stairs
Space O(N) → recursion
BottomUp_DP
```
class Solution { 
```

// Bottom Up Logic public int minCostClimbingStairs(int[] cost) {

// number of stairs that need to climb
int n = cost.length;

// DP array records the minCost of climbing to each stair
int[] dp = new int[n];

// Start from first step or the second step
dp[0] = cost[0];
dp[1] = cost[1];

// Build the dp array from bottom to up
for (int i = 2; i < n; i++) {
    dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
}

// The end point can be either last step or the last - 1 step
return Math.min(dp[n - 1], dp[n - 2]);

} }


### Complexity
- Time O(N) → to find all dp array values, n stairs
- Space O(1) → ONLY Array

mo660 commented 2 years ago

c++

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

MoonLee001 commented 2 years ago

思路

动态规划

代码

var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const 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 - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

复杂度分析：

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

caterpillar-0 commented 2 years ago

思路

动态规划

代码

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

复杂度分析

时间复杂度：o(n)
空间复杂度：o(1)

zhulin1110 commented 2 years ago

题目地址(746. 使用最小花费爬楼梯)

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

题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

 

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

 

提示：

2 <= cost.length <= 1000
0 <= cost[i] <= 999

前置知识

动态规划

代码

语言支持：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] + cost[i], dp[i - 2] + cost[i]);
    }

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

复杂度分析

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

houmk1212 commented 2 years ago

思路

动态规划+滚动数组优化

代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;

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

复杂度

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

Yongxi-Zhou 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[-1]

Yongxi-Zhou commented 2 years ago

思路

dp

代码

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]

复杂度

time O(N) space O(N)

ViviXu-qiqi commented 2 years ago

var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const dp = Array(n).fill(0);

    if (n === 1) {
        return cost[0];
    }
    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 - 2], dp[n - 1]);
};

time O(N) space O(1)

currybeefer commented 2 years ago

动态规划，dp[i]代表到达台阶n所需要的花费。目标是求dp[n]

    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n=cost.size();
        vector<int> dp(99999,n+1);
        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];
        }
        dp[n]= min(dp[n-1],dp[n-2]);
        return dp[n];
    }
    int min(int a,int b)
    {
        return a<b? a: b;
    }

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

ShawYuan97 commented 2 years ago

思路

采用动态规划的方法（带记忆的递归）
动态规划前提：最优子结构（求解的子过程都是要求上台阶花费最少）、无后向性（后面爬楼的选择不会干扰前面）

确定状态空间：台阶总数
转移方程：dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]),i>=2
枚举状态
关键点

本文定义状态空间是到达该级台阶的最小花费
其实还可以定义从该级离开的最小花费

代码

语言支持：Python3

Python3 Code:


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        """
        计算最小花费爬楼梯
        """
        n = len(cost)
        dp = [float('inf')]*n
        dp[0],dp[1] = 0,0
        for i in range(2,n):
            dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

        return min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])

复杂度分析

令 n 为数组长度。

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

Geek-LX commented 2 years ago

5.24

思路：

动态规划

代码：

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)

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

carterrr commented 2 years ago

class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length]; // 从i向上爬需要的最小花费 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]) + cost[i]; } return Math.min(dp[cost.length - 1], dp[cost.length - 2]); } }

xil324 commented 2 years ago

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        m = len(cost);
        dp = [float('inf')] * (m+1); #dp[i]: the minmium cost to climb to index i
        dp[0] = 0
        dp[1] = 0
        for i in range(2, m+1):
            dp[i] = min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]) 
        return dp[m];

time complexity: O(n);

wenliangchen commented 2 years ago

Code

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // The array's length should be 1 longer than the length of cost
        // This is because we can treat the "top floor" as a step to reach
        int minimumCost[] = new int[cost.length + 1];

        // Start iteration from step 2, since the minimum cost of reaching
        // step 0 and step 1 is 0
        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);
        }

        // The final element in minimumCost refers to the top floor
        return minimumCost[minimumCost.length - 1];
    }
}

wychmod commented 2 years ago

思路

动态规划

代码

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

复杂度分析

时间复杂度 On 空间复杂度 On

xingchen77 commented 2 years ago

思路

DP问题，状态转移

代码

    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)

Ellie-Wu05 commented 2 years ago

思路：DP

代码

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

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

复杂度

时间On 空间O1

duantao74520 commented 2 years ago

思路：动态规划

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

/ 转移方程 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]) 初始值： dp[0] = dp[1] = 0 /

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

duantao74520 commented 2 years ago

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

/ 转移方程 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]) 初始值： dp[0] = dp[1] = 0 /

空间复杂度O(1)

L-SUI commented 2 years ago


/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    let n = cost.length;
    let pre = cost[0]; 
    let next = cost[1]; 
    for(let i = 2;i < n;i++){
        let tmp = next;
        next = Math.min(pre,next)+cost[i];
        pre = tmp;
    }
    return Math.min(pre,next);
};

freedom0123 commented 2 years ago

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

zhishinaigai commented 2 years ago

思路

滚动数组减少空间消耗

代码

int minCostClimbingStairs(vector<int>& cost) {
        int len=cost.size();
        int pre=0,cur=0;
        for(int i=2;i<=len;i++){
            int next=min(cur+cost[i-1],pre+cost[i-2]);
            pre=cur;
            cur=next;
        }
        return cur;
    }

Shuchunyu commented 2 years ago

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

LQyt2012 commented 2 years ago

思路

动态规划，定义dp[i]为到达下标为i的楼梯的花费。dp[i+1]=min((dp[i-1]+cost[i-1]), (dp[i]+cost[i]))

代码

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # if len(cost) < 2:
        #     return 0
        # 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[len(cost)]
        # 优化动态数组
        dp = [0] * 3
        for i in range(2, len(cost)+1):
            dp[2] = min((dp[0]+cost[i-2]), (dp[1]+cost[i-1]))
            dp[0] = dp[1]
            dp[1] = dp[2]
        return dp[2]

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

func min(i, j int) int {
    if i <= j {
        return i
    }
    return j
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N), 优化后O(1)

miss1 commented 2 years ago

思路

爬楼梯问题， f(n) = Math.min(f(n-2), f(n-1)) + f(n)。到第n阶的花费等于到n-1阶和到n-2阶中花费的更小值加上当先花费。要求走完所有台阶，可以由最后一格或者倒数第二格到达，所以返回值是取两个中的最小值。

代码

var minCostClimbingStairs = function(cost) {
  let a = cost[0], b = cost[1];
  for (let i = 2; i < cost.length; i++) {
    let res = Math.min(a, b) + cost[i];
    a = b;
    b = res;
  }
  return Math.min(a, b);
};

复杂度

time: O(n)
space: O(1)

XXjo commented 2 years ago

思路

dp

代码

var minCostClimbingStairs = function(cost) {
    let n = cost.length;
    let dp = Array(n + 1).fill(0); //表示到第i个台阶的最优花费
    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];
};

复杂度分析

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

revisegoal commented 2 years ago

dp

状态定义：dp[i] = 到达第 i 阶所需的最小花费

状态转移：第 i 个台阶要么是第 i - 1个台阶花费cost[i - 1]上来的，要么是第 i - 2 个台阶花费cost[i - 2]上来的，我们取最小所以状态转移方程为 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

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];
}
}

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

liuguang520-lab commented 2 years ago

思路

使用dp[n]表示到达第n层所需要的最小花费，基础事件dp[0] = dp[1] =0，状态转换方程为前两个dp值加上对应位置的花费的最小值

code

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< dp.size(); i++)
        {
            dp[i] = min(dp[i-1]+ cost[i-1], dp[i-2] + cost[i-2]); 
        }
        return dp.back();
    }
};

复杂度分析

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

zenwangzy commented 2 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< dp.size(); i++)
        {
            dp[i] = min(dp[i-1]+ cost[i-1], dp[i-2] + cost[i-2]); 
        }
        return dp.back();
    }
};

houyanlu commented 2 years ago

思路

台阶问题稍微变了一下，一个dp数组，第i项跟前两项有关，取i-1和i-2到i的费用总和最小的

代码


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

        return dp[cost.size()];
    }
};

复杂度分析

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

KWDFW commented 2 years ago

Day54

746、使用最小花费爬楼梯

javascript #动态规划

思路

1、求最优解且每一步之间不会互相影响，故为动态规划

2、dp[i]:到达i阶梯的最小花费,可用cost[i-1]或者cost[i-2]表示到达下一步的花费,dp[i-1]或dp[i-2]表示达到i阶梯之前的最小花费

3、故状态转移方程为：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

4、设初值并求出dp[n]，得到最优解

代码

var minCostClimbingStairs = function(cost) {
  const n=cost.length
  const dp=new Array(n+1)
  dp[0]=dp[1]=0//可选0或1，故最小花费都是0
  for(let 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)

yinhaoti commented 2 years ago

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        """
        dynamic programming
        TC: O(n)
        SC: O(n)
        """
        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]

yangyuhuan commented 2 years ago

var minCostClimbingStairs = function(cost) { const n = cost.length; let p = 0, q = 0, tmp; for (let i = 2; i <= n; i++) {

        tmp = q;
        q = Math.min(p + cost[i - 2], q + cost[i - 1]);
        p = tmp;

    }

    return q

};

tensorstart commented 2 years ago

思路

dp mincost[i]=Math.min(mincost[i-1]+cost[i],mincost[i-2]+cost[i-1]);

代码

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

复杂度分析

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

sallyrubyjade commented 2 years ago

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    cost.push(0);
    let n = cost.length;
    let dp = [];
    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];
};

AConcert commented 2 years ago

var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const dp = new Array(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];
};

linjunhe commented 2 years ago

Code

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

复杂度分析

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

taojin1992 commented 2 years ago

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        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]: dp[i - 1], dp[i-2], cost[i]
            // careful of index
            if (i < cost.length) {
                dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
            }
            else {
                dp[i] = Math.min(dp[i-1], dp[i-2]);
            }
        }
        return dp[cost.length];
    }
}

maggiexie00 commented 2 years ago

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]

ShuqianYang 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]

hyh331 commented 2 years ago

Day3 思路

dp[i]表示从爬到第i级台阶的最少费用
因为可以直接从第0和第1阶开始，所以花费为0，dp[0]=dp[1]=0;

状态转移方程： dp[k]=min(dp[k-1]+cost[k-1], dp[k-2]+cost[k-2])，表示到达第k阶最少费用 = 到达第k-1阶的最少费用+离开本阶的费用和到达第k-2阶的最少费用+离开本阶的费用取最小值

class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
    int n=cost.size();
    //dp[]表示从爬到第i级台阶的最少费用 
    vector<int> dp(n+1,0);
    //因为可以直接从第0和第1阶开始，所以花费为0
    dp[0]=dp[1]=0;
    for(int k=2; k<=n; k++){
        dp[k]=min(dp[k-1]+cost[k-1], dp[k-2]+cost[k-2]);
    }
    return dp[n];
}
};

复杂度分析

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

flyzenr commented 2 years ago

Code

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 楼梯的长度
        n = len(cost)
        # 设计一个状态变量，存储当前台阶的花费
        dp = [0]*n
        # 初始化，开头的两个台阶
        dp[0], dp[1] = cost[0], cost[1] 
        for i in range(2,n):
            # 每个台阶的位置的状态最优解，也就是花费金额最少的，要么是从i-2跳过来，要么是从i-1跳过来
            dp[i] = min(dp[i-2],dp[i-1]) + cost[i]
        #最后两个台阶都可以直接到达楼顶，那么返回他们两个中花费少的那个
        return min(dp[-2],dp[-1])

复杂度

-时间：O(N)
-空间：O(N)

xiayuhui231 commented 2 years ago

代码

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

xiayuhui231 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< dp.size(); i++) { dp[i] = min(dp[i-1]+ cost[i-1], dp[i-2] + cost[i-2]); } return dp.back(); } };

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

【Day 54 】2022-05-24 - 746.使用最小花费爬楼梯 #59

746.使用最小花费爬楼梯

入选理由

题目地址

前置知识

题目描述

Idea

Code

Complexity

Code

C++

Solution 1

Solution 2

Idea

Code

TopDown_DP

Complexity

BottomUp_DP

c++

思路

代码

思路

代码

复杂度分析

题目地址(746. 使用最小花费爬楼梯)

题目描述

前置知识

代码

思路

代码

复杂度

思路

代码

复杂度

思路

关键点

代码

5.24

time complexity: O(n);

Code

思路

代码

复杂度分析

思路

代码

复杂度

思路：DP

代码

复杂度

思路

代码

思路

代码

复杂度分析

思路

代码

复杂度

思路

代码

复杂度分析

dp

思路

code

复杂度分析

思路

代码

javascript #动态规划

思路

代码

复杂度分析

思路

代码

复杂度分析

Code

复杂度分析

Day3 思路

复杂度分析

Code

复杂度