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)
