动态规划之——爬楼梯

LeetCode70. 爬楼梯

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

---

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
第i阶可以由以下两种方法得到：

1.在第i−1阶后向上爬1阶。
2.在第i−2阶后向上爬 2 阶。

所以到达第i阶的方法总数就是到第i−1阶和第i−2阶的方法数之和。
状态转移方程：dp[i] = dp[i-1] + dp[i-2]

Python代码：

class Solution:
    def climbStairs(self, n):
        if n <= 2:
            return n
        pre2, pre1 = 1, 2
        for i in range(2, n):
             pre1 = pre2 + pre1
             pre2 = pre1 - pre2
        return pre1

---

LeetCode764. 使用最小花费爬楼梯

题目描述：

数组的每个索引做为一个阶梯，第i个阶梯对应着一个非负数的体力花费值cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为0或1的元素作为初始阶梯。

---

每次爬一个或两个楼梯，到达楼顶前的最后一个位置只能是倒数第一个或倒数第二个楼梯，故要比较倒数第一和倒数第二所花代价哪个最小，即为到达楼顶最小代价。到达第i个位置所花最小代价为：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
其实，这里楼顶对应的代价cost[i]可以认为是零。

Python代码：

class Solution:
    def minCostClimbingStairs(self, cost):
        if len(cost) == 2:
            return min(cost)
        pre2 = cost[0]
        pre1 = cost[1]
        for i in range(2, len(cost)):
            tmp = min(pre2, pre1) + cost[i]
            pre2 = pre1
            pre1 = tmp
        return min(pre1, pre2)