1. 从买书到完全背包：一个生活化的算法入门
记得我第一次参加信息学奥赛培训时，老师用买书的例子讲解动态规划，那种"啊哈时刻"至今难忘。完全背包问题听起来很抽象，但把它想象成在书店买书就立刻变得亲切起来。假设书店有四种书，价格分别是10元、20元、50元和100元，你手上有n元钱，问有多少种买书的方案？这就是OpenJudge上经典的"买书"题目。
完全背包问题的核心特点是：每种物品（在这里是每种书）可以选取无限次。这和我们平时购物场景完全一致——你可以买0本、1本或多本同样的书。我刚开始学算法时，总把完全背包和01背包搞混，直到用买书的例子才彻底明白。01背包像是限量版商品每人限购一件，而完全背包就是普通商品想买多少买多少。
动态规划的魅力在于，它把一个看似复杂的问题分解成小问题来解决。在买书问题中，我们不需要一次性考虑所有书的组合，而是先思考"如果只考虑前i种书，花j元钱有多少种买法"，这就是dp[i][j]的状态定义。这种思维方式在解决实际问题时特别有用，比如我在准备NOI竞赛时，遇到类似的问题就会先问自己：能不能拆解成更小的子问题？
2. 状态定义：把购物车变成数学模型
2.1 理解状态定义的三个维度
定义dp[i][j]为"在前i种书中选择，总花费恰好为j元的方案数"，这个状态包含三个关键维度：
- 物品范围：前i种书，相当于购物时考虑的商品种类
- 容量限制：总花费j元，相当于你的预算
- 目标属性：方案数，这里不是求最大价值而是计算有多少种买法
我刚开始总是混淆状态定义，直到用实际数据验证才明白。比如当i=2（只有10元和20元的书），j=30时：
- 买三本10元的书
- 买一本10元和一本20元的书 所以dp[2][30]=2。这种具体化的例子帮助我真正理解了状态含义。
2.2 初始条件的陷阱
最容易出错的是初始条件设置。dp[i][0]=1表示"花0元的方案有一种——什么都不买"，这很直观。但dp[0][j]=0（j>0）表示"没有书可选时不可能花钱"，这点经常被忽略。记得有次比赛我就栽在这个边界条件上，现在每次写代码都会特意检查。
在实际编码中，我习惯这样初始化：
dp = [[0]*(n+1) for _ in range(m+1)] for i in range(m+1): dp[i][0] = 1 # 任何情况下，花费0元都有1种方案3. 状态转移：决策的艺术
3.1 分解购买决策
状态转移方程dp[i][j] = dp[i][j-a[i]] + dp[i-1][j]包含两个关键决策：
- 选择买第i种书：既然可以买无限本，买了之后还可以继续买，所以是dp[i][j-a[i]]
- 选择不买第i种书：那就只能在前i-1种书中选择，对应dp[i-1][j]
这就像在收银台做决定：拿一本当前书放进购物车，或者跳过这本书。我在白板上画决策树时，发现这和实际购物思维完全一致——"这本要吗？要的话可以再拿，不要就看下一本"。
3.2 从二维到一维的优化
原始二维数组会占用O(nm)空间，通过观察可以发现只需要前一行的数据，于是可以优化为一维数组：
dp = [0]*(n+1) dp[0] = 1 # 初始化 for price in book_prices: for j in range(price, n+1): dp[j] += dp[j - price]这个优化技巧在竞赛中特别实用，我把它叫做"滚动购物车"法。不过要注意内层循环必须正序，因为完全背包允许重复选取，这和01背包的逆序循环正好相反。
4. 实战演练：OpenJudge真题解析
4.1 题目细节分析
OpenJudge 6049题给出了具体书的定价：[10,20,50,100]。这组数据很有教学意义：
- 包含倍数关系（20是10的倍数，100是50的倍数）
- 数值跨度适中，适合验证各种边界情况
我在本地测试时发现一些有趣现象：
- 当n<10时，方案数为0（最便宜的书都买不起）
- 当n=20时，有2种方案（20×1或10×2）
- 当n=100时，方案数突然增加到11种
4.2 调试技巧分享
在实现过程中，我习惯添加调试输出：
def buy_books(n): prices = [10, 20, 50, 100] dp = [0]*(n+1) dp[0] = 1 for i, price in enumerate(prices, 1): for j in range(price, n+1): old = dp[j] dp[j] += dp[j - price] print(f"加入第{i}种书({price}元): dp[{j}] = {old} + {dp[j-price]} = {dp[j]}") return dp[n]这样能清晰看到每个决策如何影响结果。比如当n=30时，输出会显示：
加入第1种书(10元): dp[10] = 0 + 1 = 1 加入第1种书(10元): dp[20] = 0 + 1 = 1 ... 加入第2种书(20元): dp[20] = 1 + 1 = 2这种可视化方法帮助我快速定位过一个bug：内层循环的起始值设置错误。
5. 竞赛中的变式与应对策略
5.1 常见变式题型
在NOI等竞赛中，完全背包求方案数可能以各种形式出现：
- 货币兑换问题：给定不同面额硬币凑成指定金额
- 物品组合问题：如选择实验器材搭配方案
- 路径计数问题：当步长可重复时的走法统计
我遇到过一个变式题：每种书有库存限制（不是无限）。这看似像多重背包，但通过巧妙转化仍能用完全背包思路解决。关键是把有限库存拆分成不同"虚拟书"，比如5本20元的书可以看作20、40、60、80、100元的五种选择。
5.2 性能优化经验
当n很大时（比如1e5），常规解法可能超时。我总结的优化技巧包括：
- 提前终止：如果当前最小书价是10元，那么n<10时直接返回0
- 因数分解：当所有书价有公约数时，可以等比例缩小问题规模
- 数学组合：对于特殊价格序列（如等比数列），可能存在公式解
在区域赛中曾遇到n=1e5的案例，通过预处理书价的GCD，将问题规模缩小10倍，成功在时限内通过。这提醒我们：算法竞赛中，数学洞察力有时比蛮力计算更重要。
