题目

LeetCode.746.使用最小花费爬楼梯（简单）

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

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

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

题解

思路

最优化问题，往动态规划上考虑，看是否符合动态规划的条件：最优子结构、重叠子问题、无后效性。
一般从最终状态做倒推，拆分步骤，列出所有到达最终状态的步骤，看能否拆分为上一个同性质的子问题+有限步骤，拆分步骤的过程得出状态转移方程。

cost数组长度为n，到达楼顶就是到达下标n的地方。
设dp[i]表示达到到达下标i所需的最小花费，0 <= i <= n。

初始边界

可以从下标为0或1的阶梯开始爬，说明dp[0] = dp[1] = 0。

划分子问题

达到第i个阶梯，最后一步有两种选择：

在第i-1层爬1个阶梯。
在第i-2层爬2个阶梯。

到达第i-1层的最小花费是dp[i-1]，爬1个阶梯需要耗费cost[i-1]
到达第i-2层的最小花费是dp[i-2]，爬2个阶梯需要耗费cost[i-2]
那么，到达第i层阶梯就是取两者中较小值。

状态转移方程

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

空间优化

dp[i]只与前两项值有关，所以不需要数组，用两个变量保存前面两项值即可。

代码

class Solution {
    fun minCostClimbingStairs(cost: IntArray): Int {
        var cur = 0
        var pre1 = 0
        var pre2 = 0
        for (i in 2..cost.size) {
            cur = minOf(pre1 + cost[i - 1], pre2 + cost[i - 2])
            pre2 = pre1
            pre1 = cur
        }
        return cur
    }
}