Python动态规划初步

用“记账本”思路学动态规划——从爬楼梯开始

你有没有遇到过这样的问题：要完成一件事，有很多种不同的做法，而且每一步的选择会影响到后续的结果？比如，你想用1元和2元的零花钱凑出10元钱，有多少种凑法？或者，你每天可以背5个单词或10个单词，一周能背完多少个？这些问题如果一步步硬算，会非常麻烦，而且很多重复。动态规划（Dynamic Programming，简称DP）就像一本聪明的记账本，它会把已经算过的结果记下来，下次需要时直接拿来用，避免重复劳动，从而快速高效地解决问题。

今天，我们就用最常见的“爬楼梯”问题来学习动态规划的基础。学完之后，你会发现自己也能像小侦探一样，轻松解决很多看似复杂的问题。

什么是动态规划？——从爬楼梯说起

想象一下，你要爬一个10级的楼梯，每次可以走1级或2级。问：有多少种不同的爬法？

如果你从第1级开始数，比如：1→2→3→... 或者 1→3→... 你会发现，相同的小段路径会重复出现很多次。比如，爬到第8级的方法，用递归硬算的话，可能被重复计算几十遍。而动态规划的做法是：先算出爬到第1级、第2级的走法，然后一步步算出第3级、第4级……直到第10级。每算出一个结果，就记在本子上，后面要用直接翻本子。

生活类比：假设老师让你统计全班同学一周内一共拿到了多少颗星星。如果每个同学单独报数，然后你一个一个累加，容易加错。动态规划的思路是：先算第一个同学的星星数，记下；然后第二个同学的加上第一个的，记下；第三个加上第二个的……这样你只需要记住一个累加数，就能快速得到最后的总数。动态规划就是这种“边算边记，用已知推未知”的方法。

核心思想：拆解、记忆、递推

动态规划有三个关键步骤，我们用一个表格来理解：

把大问题拆成小问题
问题：爬到第10级楼梯有多少种方法？
拆解：最后一步要么是从第9级走1步，要么是从第8级走2步。
所以：爬到第10级的方法数 = 爬到第9级的方法数 + 爬到第8级的方法数。
同样，爬到第9级的方法数 = 爬到第8级的方法数 + 爬到第7级的方法数……不断拆下去。
记住小问题的答案
用列表（数组）把每个台阶的方法数存下来，比如dp[1]表示爬到第1级的方法数，dp[2]表示爬到第2级的方法数。这样，当需要用到dp[8]时，直接从列表里取，不用再算一遍。
从小到大计算（递推）
先算出最基础的台阶：
- 第0级（还没爬）：只有一种方法——不动，所以dp[0]=1
- 第1级：只能走1步（1种），所以dp[1]=1
- 第2级：可以1+1或直接2（2种），所以dp[2]=2
  然后从第3级开始，用公式dp[i] = dp[i-1] + dp[i-2]依次算出所有直到第n级。

为什么叫“动态规划”？
“规划”是指我们像制定计划一样，一步步推导出答案；“动态”是因为每一步的决策（走1级还是2级）会影响后续结果，但我们的记账本不会变，所以叫“动态”。（记住这个名字就好，不用深究）

代码示例：爬楼梯问题（详细版）

下面这个Python程序，输入楼梯级数n，输出爬法总数。我们给每行代码都加上中文注释，方便理解。

def climb_stairs(n):
    # 如果楼梯级数少于等于1，直接返回1（0级1种，1级1种）
    if n <= 1:
        return 1
    
    # 创建列表dp，长度为n+1，用来存储爬到每级台阶的方法数
    # dp[i]表示爬到第i级台阶的方法数
    dp = [0] * (n + 1)
    
    # 初始化基础台阶
    dp[0] = 1  # 第0级（起点）：一种方法（不动）
    dp[1] = 1  # 第1级：一种方法（直接跨1步）
    
    # 从第2级开始，逐个计算到第n级
    for i in range(2, n + 1):
        # 公式：爬到第i级的方法数 = 爬到第i-1级的方法数 + 爬到第i-2级的方法数
        dp[i] = dp[i-1] + dp[i-2]
    
    # 返回第n级的方法数
    return dp[n]

# 测试：爬10级楼梯有多少种方法？
print(climb_stairs(10))  # 输出结果：89

运行结果：当输入10时，输出89。这意味着爬10级楼梯，每次走1或2级，共有89种不同的爬法。

代码图解（简单理解）：

dp = [0, 0, 0, ...] 就像一个记账格子，从0号格子到n号格子。
我们先填好dp[0]=1和dp[1]=1。
然后for循环依次填dp[2]、dp[3]……直到dp[n]。
每次填的时候，只需要看前面两个格子的值，把它们加起来即可（因为最后一步只可能来自前1级或前2级）。

常见错误（新手最容易犯的坑）

索引越界
比如忘记给dp分配足够的长度（n+1），或者循环时range(2, n+1)写成了range(2, n)，导致最后一个dp[n]没有被计算。
✅ 记住：列表长度一定要是n+1，循环到n+1（不包括n+1，所以循环到n）。
初始条件搞错
- 有人认为dp[0]应该为0，但为了公式统一（比如dp[2]=dp[1]+dp[0]），dp[0]应该为1，表示“不动”也是一种方法。如果你把dp[0]设为0，那么dp[2]就会变成1+0=1，但实际有2种爬法（1+1和2），就错了。
  ✅ 记住：0级台阶有1种方法（站着不动），1级有1种方法（直接走1步）。
忘记处理边界条件
当n=0或n=1时，程序直接返回1。如果不加if n <= 1: return 1，那么执行dp[0]=1, dp[1]=1后，如果n=0，循环for i in range(2, 1)根本不会执行，但最后返回dp[0]也是正确的。但为了代码清晰和安全，显式处理边界更好。
混淆“第几级”和“列表索引”
- 如果楼梯有n级，我们需要的列表长度是n+1（因为要包含0级）。新手可能把dp大小设为n，然后dp[i]对应第i级，但第0级就放不下了。
  ✅ 统一：索引i代表第i级，所以列表大小至少n+1。

完整可运行示例（带输入提示）

下面是一个可以直接复制运行的完整程序，用户输入楼梯级数，程序输出爬法总数。

def climb_stairs(n):
    # 如果楼梯级数少于等于1，直接返回1
    if n <= 1:
        return 1
    
    # 创建dp列表，长度为n+1，初始化为0
    dp = [0] * (n + 1)          # dp[i]表示爬到第i级的方法数
    dp[0] = 1                    # 第0级（起点）：1种方法
    dp[1] = 1                    # 第1级：1种方法（跨1步）
    
    # 从第2级开始递推
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]   # 最后一步来自i-1或i-2
    
    return dp[n]

# 主程序：让用户输入楼梯级数
if __name__ == "__main__":
    try:
        n = int(input("请输入楼梯级数（例如10）："))
        if n < 0:
            print("楼梯级数不能为负数！")
        else:
            result = climb_stairs(n)
            print(f"爬 {n} 级楼梯，每次爬1级或2级，共有 {result} 种方法。")
    except ValueError:
        print("请输入一个整数。")

运行示例：

请输入楼梯级数（例如10）：10
爬 10 级楼梯，每次爬1级或2级，共有 89 种方法。

生活中的其他动态规划问题

动态规划不仅能爬楼梯，还能解决很多和生活相关的问题。这里举两个例子：

1. 零花钱凑数问题
你有1元和2元的硬币，想凑出10元钱，问有多少种凑法？这和爬楼梯一模一样！每次你选择加1元或2元，凑到10元的方法数，就是从0元开始，每次加1或2，最终到达10元的路径数。所以代码几乎不用改，只需要把楼梯级数改成总金额即可。

2. 考试得分问题
一次考试有10道判断题，每道题答对得1分，答错得0分。放学后你可以选择复习哪些题目。如果你每天只能复习1道题或2道题，问期末前一共有多少种复习进度安排？其实也是爬楼梯的变种：把“第i天”看作“第i级台阶”，每天选择复习1题或2题，问复习完10道题有多少种顺序。结果同样是89种。

3. 排队买冰淇淋
你和朋友排队买冰淇淋，队伍长度是n。每次你可以一个人先买，也可以两个人一起买（假设两个人一起买速度一样）。问有多少种排队顺序？这本质上就是爬楼梯。