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)