数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python 最小成本爬楼梯
假设有一座楼梯，其中第 i 级台阶会分配一些非负成本值 cost[i]。当我们支付成本时，我们可以爬上一级或两级台阶。我们必须找到到达楼层顶部的最低成本，我们也可以从索引为 0 或索引为 1 的台阶开始。
因此，如果输入类似于 cost = [12,17,20]，则输出将为 17，因为从步骤 1 开始是最便宜的，因为我们必须支付该成本并到达顶部。
为了解决这个问题，我们将遵循以下步骤：
- dp := 一个与 cost 大小相同的数组，并填充 0
- dp[0] := cost[0]
- 如果 cost 的大小 >= 2，则
- dp[1] := cost[1]
- 对于 i 从 2 到 cost 的大小 - 1，执行以下操作：
- dp[i] := cost[i] + dp[i-1] 和 dp[i-2] 中的最小值
- 返回 dp[-1] 和 dp[-2] 中的最小值
让我们看看下面的实现，以便更好地理解：
示例
class Solution: def minCostClimbingStairs(self, cost): dp = [0] * len(cost) dp[0] = cost[0] if len(cost) >= 2: dp[1] = cost[1] for i in range(2, len(cost)): dp[i] = cost[i] + min(dp[i-1], dp[i-2]) return min(dp[-1], dp[-2]) ob = Solution() print(ob.minCostClimbingStairs([12,17,20]))
输入
[12,17,20]
输出
17
更新于：2020年7月4日
634 次浏览
广告