动态规划

算法教程 · 第 6 章 · 6 次浏览

动态规划（DP）解决"最优子结构 + 重叠子问题"：把大问题拆成小问题，小问题的答案存起来复用，避免重复计算。

DP 四步

定义状态：dp[i] 表示什么
状态转移：dp[i] 怎么由前面的推出来
初始化：dp[0] 等边界值
结果：答案在哪个 dp 里

经典问题

爬楼梯、背包、最长公共子序列、最长递增子序列。

代码示例

# 爬楼梯：每次爬 1 或 2 阶，n 阶有几种爬法
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 到 i 阶 = 到 i-1 阶爬1 + 到 i-2 阶爬2
    return dp[n]

print(climb_stairs(10))    # 89

# 0/1 背包：容量 W，物品价值和重量，最多装多少
def knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

print(knapsack([2, 3, 4], [3, 4, 5], 5))    # 7

📚 Python 语法速查

常用条目速查，完整版见对应教程章节。可复制代码到在线运行中测试。

写法 / 语法	作用
`print("hello")`	输出到控制台
`name = "张三"`	变量赋值（无需声明类型）
`if x > 0: ...`	条件判断（注意冒号和缩进）
`for i in range(10): ...`	循环（缩进是语法的一部分）
`while x < 10: ...`	条件循环
`def fn(a, b): return a + b`	定义函数
`class Person: ...`	定义类
`list = [1, 2, 3]`	列表（可改）
`tuple = (1, 2)`	元组（不可改）
`dict = {"key": "value"}`	字典（键值对）
`set = {1, 2, 3}`	集合（去重）
`len(obj)`	取长度
`str(x) / int(x) / float(x)`	类型转换
`s.split(",")`	字符串按分隔符拆分
`" ".join(list)`	列表拼接成字符串
`import os`	导入模块
`from math import sqrt`	从模块导入指定函数
`try: ... except Exception as e: ...`	异常捕获
`with open("a.txt", "r") as f: ...`	文件读取（自动关闭）
`f"你好 {name}"`	f-string 格式化
`lambda x: x * 2`	匿名函数
`list(map(fn, arr))`	函数式处理列表
`range(start, stop, step)`	生成数字序列
`if __name__ == "__main__":`	主入口判断
`pip install 包名`	安装第三方包（命令行）