1. 题目在问什么先把金字塔翻译成公式UVa 1110 的题名是 Pyramids光看这个词很容易往三维几何、体积公式上想。我第一次做这道题时还真去算了半天金字塔体积结果发现题目根本不在乎体积它在乎的是给你 N 个球能摆出多少种不同的金字塔组合。这里的金字塔是那种每一层都是正方形的球堆最上面一层 1 个球第二层 4 个球第三层 9 个球第 h 层就是 h² 个球。所以一座高度为 h 的完整金字塔需要的球数是S(h) 1² 2² 3² ... h² h(h 1)(2h 1) / 6这个数也叫方形金字塔数square pyramidal number前几项是hS(h)1125314430555691题目给你一个 N问的是用若干个这样的 S(h) 加起来刚好凑成 N一共有多少种不同的凑法。每座金字塔的高度可以任意取同一个高度也可以出现多次方案只关心每种高度用了多少次不关心摆放顺序。也就是问你N 能拆分成多少个方形金字塔数的无序组合。举个例子N 5 时有两种方案用五座高度为 1 的金字塔1 1 1 1 1用一座高度为 2 的金字塔1² 2² 5N 14 时有四种十四个 11 个 5 加九个 12 个 5 加四个 11 个 14到这一步题目就从摆放球变成了一个非常经典的计数问题。为什么要这样转化因为直接枚举金字塔高度的组合会爆炸而一旦把它看成硬币找零动态规划的思路就顺理成章了。2. 动态规划方程和循环顺序为什么答案不是排列数把金字塔数当成硬币这个问题就等价于有面值为 S(1), S(2), S(3), ... 的硬币每种硬币无限量问凑出 N 元有多少种组合方式。组合和排列的区别在于1 5 和 5 1 在这里是同一种方案不能算两次。这是整道题最容易写错的地方。2.1 状态定义定义 dp[x] 表示凑出 x 个球有多少种方案。边界条件是dp[0] 1它的含义是用 0 座金字塔凑出 0 个球这在递推中是必要的不然所有转移都从哪儿开始从它开始每加入一种面值的金字塔就相当于给所有已有的方案追加若干个这种面值。最终答案就是 dp[N]。2.2 转移方程假设当前处理到金字塔高度 h对应的面值是 c S(h)那么对于任意 x ≥ c有dp[x] dp[x - c]这个式子看起来简单但要小心这里的 x 必须从小到大循环因为同一种金字塔可以用多次。如果你让 x 从大到小循环每轮每种面值最多只用一次那就变成了 0/1 背包答案会少很多。2.3 为什么外层必须是金字塔高度这是最关键的一个点也是我当年第一次提交 WA 的原因。正确写法是for each coin c: for x c to N: dp[x] dp[x - c]错误写法是for x 0 to N: for each coin c: if x c: dp[x] dp[x - c]两种写法在数字上有本质区别。正确写法中coins 的顺序是固定的相当于先决定用多少个 S(1)再决定用多少个 S(2)再决定用多少个 S(3)…… 这样生成出来的每种方案只有一种产生路径不会因为先放 5 再放 1和先放 1 再放 5而重复计数。错误写法里dp[x] 会从所有可能的前一个状态累加过来本质是在数排列而不是组合。比如用面值 1 和 5 凑 6组合只有两种6 个 1或者 1 个 5 和 1 个 1。但排列数会认为15和51是两种给出 3 个结果。把这种错误带到 N 很大的时候答案差得离谱。所以写这题时第一件事就是记住外层循环遍历金字塔高度内层循环遍历容量。这个顺序就是组合计数和排列计数的分水岭。3. 可直接 AC 的完整代码C / Python思路清楚了代码其实很短。我一般会先把所有不超过题目上限 N 的金字塔数预处理出来然后跑一遍完全背包。3.1 预处理金字塔数列表金字塔数的公式是 h(h 1)(2h 1) / 6。这里有个小陷阱公式里的乘积在 h 比较大时会超过 32 位整数范围所以中间变量不要用 int建议直接用 long long。假设题目上限是 10^6那么算到第 143 项就已经超过 100 万了实际需要的金字塔数只有一百多个非常少。预处理的循环可以写成vectorlong long coins; for (long long h 1; ; h) { long long p h * (h 1) * (2 * h 1) / 6; if (p MAXN) break; coins.push_back(p); }3.2 C 核心代码#include bits/stdc.h using namespace std; const int MAXN 1000000; int main() { vectorunsigned long long coins; for (long long h 1; ; h) { long long p h * (h 1) * (2 * h 1) / 6; if (p MAXN) break; coins.push_back((unsigned long long)p); } vectorunsigned long long dp(MAXN 1, 0); dp[0] 1; for (unsigned long long c : coins) { for (int x (int)c; x MAXN; x) { dp[x] dp[x - (int)c]; } } int n; while (cin n) { if (n 0) break; cout dp[n] \n; } return 0; }后面的输入输出部分按题目要求通常读到 0 结束。如果你不确定是 EOF 还是 0建议写成while (cin n n)这样两种都能兼容。3.3 Python 参考实现import sys MAXN 10**6 coins [] h 1 while True: p h * (h 1) * (2 * h 1) // 6 if p MAXN: break coins.append(p) h 1 dp [0] * (MAXN 1) dp[0] 1 for c in coins: for x in range(c, MAXN 1): dp[x] dp[x - c] for line in sys.stdin: n int(line.strip()) if n 0: break print(dp[n])Python 版本如果每次都从 1 到 10^6 跑一百四十三层循环的加法次数大概 1.4 亿次在 PyPy 下可以过但在 CPython 下可能会比较吃紧。一个很实用的优化是先把所有输入读进来找到其中最大的 N然后只把 dp 开到 maxN而不是固定开 1000000。这样实际测试数据如果很小跑得会快很多。4. 实际提交时容易踩的三个坑代码短归短UVa 上这道题还是有不少人 WA我把自己踩过的和帮别人看过的坑总结一下。4.1 dp 数组类型选太小这个问题的答案增长速度比你想的快。虽然金字塔数的个数只有一百多个但组合数量并不小。比如稍微大一点的 N答案是百万甚至十亿级别的。如果你用int存 dp很容易在不知不觉中溢出然后得到一堆负数或奇怪的大数。我的习惯是直接用unsigned long long或long long。如果题目要求取模就根据模数用int 取模运算。UVa 1110 原题没有取模所以 64 位比较稳妥。4.2 公式中间变量用 int 提前溢出h * (h 1) * (2 * h 1)在 h 10000 时大约是 10^12早就超过 32 位 int 的范围了。虽然题目给你的 N 可能只有 10^6预计算时循环到 h ≈ 144 就停了此时 int 不会爆。但如果你把 MAXN 调大到 10^8或者换到别的题目里沿用这段代码忘记把 h 声明成 long long 就会出问题。所以预处理公式里所有乘法因子都用长整型别省这一下。4.3 把读入结束条件写错UVA 很多题用 0 表示输入结束但也有些直接用 EOF。Pyramids 这题的输入是多个测试用例以 0 结束。如果你只写while (cin n)那读到 0 时还会输出一个 dp[0] 1导致答案错一位。正确做法是读进来先判断如果是 0 就 break不参与输出。4.4 忘了上一层循环的作用域还有一个小坑是内层循环的起点。for (int x c; x N; x)起点必须是当前硬币面值 c不能从 1 开始。从 1 开始虽然也能跑但会访问 dp[x - c] 的负下标或者需要 if 判断白白增加代码复杂度。从 c 开始是无懈可击的写法。5. 复杂度分析和一点优化思路5.1 复杂度设 T 是小于等于 N 的金字塔数个数。由于 S(h) 约等于 h³ / 3T ≈ (3N)^(1/3)。当 N 10^6 时T 143。DP 的时间复杂度是 O(T * N)空间复杂度 O(N)。看起来 O(T * N) 有点吓人但 T 实在太小了。N 10^6 时只需要大约 1.4 亿次加法C 跑一遍不到 0.2 秒。即使 N 到 10^7T 也只有三百多三千万次加法的量级依然很快。这就是把问题数学化之后带来的好处表面上 N 很大但候选硬币的数量是立方根量级的。5.2 还能不能更快如果你想追求极限可以在预处理时把 dp 数组类型换成uint64_t并且把内层循环写成指针操作减少数组索引带来的开销。但说实话对这道题没必要。UVa 的单点数据量很小主要的耗时在读入和输出而不是 DP。Python 版本最大的优化是动态 maxN。先读全部输入nums [] for line in sys.stdin: n int(line.strip()) if n 0: break nums.append(n) maxN max(nums) if nums else 0然后只预处理到 maxN最后再输出。这样如果实际数据最大只有几万速度会非常快。5.3 生成函数视角如果从生成函数的角度看这个问题的答案就是F(x) 1 / ((1 - x)(1 - x^5)(1 - x^14)(1 - x^30)...)其中 x^N 的系数就是 dp[N]。生成函数能帮你快速理解为什么外层循环是金字塔高度因为每一项对应一个因子逐个乘进去就是把一个因子一层一层展开。这个视角在做类似题目时非常有用尤其是当你需要推导最多用多少次或者最少用多少个的时候。6. 这类题还能怎么举一反三UVa 1110 本质上是一道完全背包求方案数的题但它被一层金字塔的外壳包住了很多新手会卡在建模这一步。一旦你把外壳扒掉就能应用到很多变体。6.1 改成每座金字塔最多用一次如果题目改成每种高度的金字塔最多只能用一座那么 DP 就从完全背包退化成 0/1 背包。唯一要改的只有内层循环方向for (long long c : coins) { for (int x MAXN; x (int)c; --x) { dp[x] dp[x - (int)c]; } }从大到小遍历容量就能保证每个面值只被用一次。这个改动非常小但语义完全不同。做题时一定要看清楚题目有没有每种尺寸最多一个这样的限制。6.2 改成求最少用多少座金字塔如果把方案数改成最少需要几座金字塔状态定义就变成 dp[x] 表示凑出 x 个球最少需要多少座金字塔转移时取 min。初始化 dp[0] 0其余为无穷大for (long long c : coins) { for (int x c; x MAXN; x) { dp[x] min(dp[x], dp[x - c] 1); } }这个变体在实际面试里更常见因为最少个数比方案总数更容易被出题人拿来考。6.3 输出具体方案如果想输出每一种具体的金字塔组合怎么办那就不能只存方案数还要在转移时记录路径。通常做法是新建一个二维数组或者prev数组当 dp[x] 从 dp[x - c] 转移成功时记录下当前用的高度最后从 N 往前回溯。当然如果方案数很多你会被输出量淹没这种需求一般只会出现在小数据范围的特判里。6.4 同类型题目清单我在刷题时发现UVa 里大量题目都是这个套路只是换了硬币的生成方式UVa 674经典硬币找零面值是 1, 5, 10, 25, 50UVa 147美元面值多一个小数位转换UVa 357同类硬币计数UVa 10313硬币面值和数量的约束LightOJ 1233也是硬币组合区别是面值按二进制规律生成这些题的核心代码几乎一模一样区别只在预处理面值的公式。所以 Pyramids 这道题其实是很好的母题做透之后你在考场上碰到任何某种数列 无限取 求方案数的题都能第一时间想到完全背包。我个人做这类题的一个小习惯是先把硬币列表预处理出来单独打印一遍确认前几项符合手算结果再跑 DP。比如 Pyramids 前几项必须是 1, 5, 14, 30如果算出来是别的数多半是公式写错了而不是 DP 写错。这个习惯帮我省了很多次无意义的 debug 时间。