746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

• 难度: easy
• 原始链接: https://leetcode.cn/problems/min-cost-climbing-stairs
• 标签: 动态规划

解法一: 动态规划: O(n) 空间复杂度

go

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

func min(num1, num2 int) int {
    if num1 <= num2 {
        return num1
    }
    return num2
}

解法二: 动态规划: O(1) 空间复杂度

go

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    cost1 := cost[0]
    cost2 := cost[1]
    for i := 2; i < n; i++ {
        cost1, cost2 = cost2, cost[i] + min(cost1, cost2)
    }
    return min(cost1, cost2)
}

func min(num1, num2 int) int {
    if num1 <= num2 {
        return num1
    }
    return num2
}