用 Python 实现爬楼梯的最小成本
pythonserver side programmingprogramming更新于 2023/11/9 23:07:00
假设有一个楼梯，这里的第 i 个台阶将被分配一个非负成本值 cost[i]。当我们支付成本时，我们可以爬一级或两级台阶。我们必须找到到达地板顶部的最小成本，我们也可以从索引为 0 的步骤开始，也可以从索引为 1 的步骤开始。
因此，如果输入为 cost = [12,17,20]，则输出将是 17，这是从步骤 1 开始的最便宜位置，因为我们必须支付该成本并到达顶部。
为了解决这个问题，我们将遵循以下步骤 −
- dp := 一个大小与成本相同的数组，并用 0 填充
- dp[0] := cost[0]
- 如果成本大小 >= 2，则
- dp[1] := cost[1]
- 对于 i 在 2 到成本大小 - 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
