climb_stairs_2

• 题号：—
• 来源：LeetCode
• 难度：中等
• 标签：dp
• 语言：Python
• 解法：1 个
• 作者：lmliheng
• 最近更新：2026-09-29

Python · O(n) 时间 · O(n) 空间 · 更新于 2026-09-29

dp 每次可跨 1/2/3 级，取最小花费

"""
@difficulty medium
@tags dp
@time O(n)
@space O(n)
@note dp 每次可跨 1/2/3 级，取最小花费
"""

from typing import List
class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        dp = [0] * (n + 1)
        if n == 1:
            return dp[0] + costs[0] + 1
        if n == 2:
            dp[1] = dp[0] + costs[0] + 1
            dp[2] = min(dp[0] + costs[1] + 4, dp[1] + costs[1] + 1)
            return dp[2]
        dp[1] = dp[0] + costs[0] + 1
        dp[2] = min(dp[0] + costs[1] + 4, dp[1] + costs[1] + 1)
        for i in range(3, n + 1):
            dp[i] = min(
                dp[i - 1] + costs[i-1] + 1,
                dp[i - 2] + costs[i-1] + 4,
                dp[i - 3] + costs[i-1] + 9,
            )
        print(dp)
        return dp[n]

源码：python/leetcode/climb_stairs_2.py

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm