问题

数组的每个索引做为一个阶梯，第 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] 将会是一个Integer类型，范围为 [0, 999]。

---

思路及解答

1. Python 实现

# 方法：动态规划
# DP三连：要求什么？结果怎么来？建立状态转移！
# 我的分析：
# 	要求最终的最低花费，我们用 min(cost_s(i)) 表示，它由上阶段来，上阶段有两种：一步之前、两步之前，因此建立状态转移应该是：min(cost_s(i)) = min{(cost_s(i-1))+cost(i), cost_s(i-2)+cost(i)}，这个状态转移有两种前提：从 0 开始、从 1 开始。
	class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp0, dp1 = cost[0], cost[1]  # 这里的 dp0 和 dp1 是赋初始状态
        for i in range(2, len(cost)):
            dp = cost[i] + min(dp0, dp1)  # 这个是状态转移方程，这里的 dp0 和 dp1 是指分别从 i-2 和 i-1 来的 cost 值（即可能的两种上阶段状态值）
            dp0, dp1 = dp1, dp   # 这里是指随着 i 的增加，前面两个阶段的值也在更新，类似于我画的那个简图
        return min(dp0, dp1)   # 因为最终状态可以是最后那个的索引 i 走一步，或者倒数第二个的那个索引 i-1 走两步，所以这里是两个的最小值。
		

# 这是我第一次写的，我混淆了动态规划和递归，动态规划不是函数的自调用，而其本质是状态的转移，所以哪里不应该是函数，应该是状态值来索引！
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        l = len(cost)
        for i in range(l):
            # 从 0 开始
            cost_s1 = min(minCostClimbingStairs(self, cost[0:i])+cost[i], minCostClimbingStairs(self, cost[0:i-1])+cost[i])
            # 从 1 开始
            cost_s2 = min(minCostClimbingStairs(self, cost[1:i])+cost[i], minCostClimbingStairs(self, cost[1:i-1])+cost[i])
        return min(cost_s1, cost_s2)
		

################# 网上的参考：另建立了数组，增加了空间复杂度。################
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        f = [cost[0], cost[1]]
        for i in range(2, len(cost)):
            f.append(cost[i] + min(f[i-1], f[i-2]))
        return min(f[-1], f[-2])

---

知识点

1. 关于动态规划，我的心得

(1) 动态规划不同于递归，不是函数的自调用，而是不同阶段的状态转移;

(2) 动态规划有两种实现形式：一种是建立新数组存储，空间复杂度是 O(N)；一种是直接在原数组进行操作，空间复杂度是 O(1)，在原数组进行操作相当于不断更新原两阶段的状态值，简要图说明见链接：【20190318】【每天一道算法题】爬楼梯（动态规划）