动态规划入门 - 算法入门

← 返回课程算法入门 › 第 9 关

进度 0%

第 9 关：动态规划入门

Python/C++进阶

📖 本课目标

本关属于《算法入门》第 9 课。阅读右侧代码模板，理解每一行的作用，然后动手修改并完成练习。

🎯 本课要点

动态规划入门
1. 爬楼梯问题
每次可以爬 1 或 2 个台阶，有多少种方法？

🛠 学习方式

阅读右侧代码模板中的注释与实现
修改代码，尝试达成新的效果
点击「运行」查看实际输出
确认理解后点击「提交」标记本关完成

💡 说明

本关为 Python/C++，浏览器内无法真正执行该语言。当前「运行」输出为演示结果，请在本地环境中编译运行以验证代码。

main.pytest.py

# 动态规划入门

# 1. 爬楼梯问题
# 每次可以爬 1 或 2 个台阶，有多少种方法？
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print("爬楼梯:")
for n in [3, 5, 10, 20]:
    print(f"  {n} 阶: {climb_stairs(n)} 种方法")

# 2. 最大子数组和（Kadane 算法）
def max_subarray(arr):
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(f"\n数组: {data}")
print(f"最大子数组和: {max_subarray(data)}")

# 3. 最长递增子序列
def lis(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

data2 = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"\n数组: {data2}")
print(f"最长递增子序列长度: {lis(data2)}")

# 4. 硬币找零
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 5, 10, 25]
print(f"\n硬币: {coins}")
for amt in [11, 30, 63]:
    print(f"  找零 {amt}: 最少 {coin_change(coins, amt)} 枚硬币")

点击「运行」或「提交代码」查看结果

📖 查看本课说明

第 9 关：动态规划入门

Python/C++ · 进阶 · 《算法入门》

动态规划入门
1. 爬楼梯问题
每次可以爬 1 或 2 个台阶，有多少种方法？

本关为 Python/C++，浏览器无法真正编译运行，请在本地环境验证代码。