题解 | #最小花费爬楼梯#
最小花费爬楼梯
http://www.nowcoder.com/practice/9b969a3ec20149e3b870b256ad40844e
思路：动态规划
dp[i]：爬到第i层的最小花费
每次可爬1或2阶，所以最小花费可分为两种情况：
由于是计算最小花费，所以将dp数组初始化为最大值；
由推导公式可知，每次的状态值都由前两个状态值推导而来，故初始化dp[0] = 0, dp[1] = 0，因为可从第0阶或第一阶开始
代码如下：
每次可爬1或2阶，所以最小花费可分为两种情况：
- 从i-1阶爬上来，花费为：爬到i-1阶的最小花费 + 从第i-1阶爬要花的费用，即dp[i-1] + costs[i-1]
- 从i-2阶爬上来，花费为：爬到i-2阶的最小花费 + 从第i-2阶爬要花的费用，即dp[i-2] + costs[i-2]
由于是计算最小花费，所以将dp数组初始化为最大值；
由推导公式可知，每次的状态值都由前两个状态值推导而来，故初始化dp[0] = 0, dp[1] = 0，因为可从第0阶或第一阶开始
代码如下：
n = int(input())
costs = list(map(int, input().split()))
if n <= 1:
print(0)
else:
dp = [float('inf')] * (n+1)
dp[0] = 0
dp[1] = 0
for i in range(2, n+1):
dp[i] = min(dp[i-1]+costs[i-1], dp[i-2]+costs[i-2])
print(dp[n])
投递腾讯等公司6个岗位 >
