leetcode 746 使用最小花费爬楼梯

题目

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

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

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

示例

输入：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 。

解析

感觉这道题虽然是简单，但属实不太好理解；
首先动态规划五部曲基本上没什么变化：
1.确定dp数组以及下标的含义
到达第i台阶所花费的最少体力为dp[i]；
2.确定递推公式
选最小的，dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3.dp数组如何初始化
根据新的题意，开始的那一步是不花费cost的，所以dp[0] = 0，dp[1] = 0
4.确定遍历顺序
和之前的一样
5.举例推导dp数组
等有问题的写一个试下
代码如下：

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

func min(a, b int) int {
    if a < b {
        return a 
    }
    return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17