UVa 1110 Pyramids 这道题，我在第一次刷的时候愣是抱着题目反复读了三遍，才反应过来它跟埃及金字塔没什么关系，主角其实是 square pyramidal number，也就是正方形金字塔数。说白了，题目给你一个整数 n，要你判断能不能把它拆成若干个金字塔数的和，而且用的个数要最少，最后还把每个金字塔对应的层数原样输出。这个问题放在算法竞赛里，本质就是一个非常经典的完全背包模型，但因为它披着几何的外衣，很多新手会先被题意绕晕，再被路径输出卡住。这篇文章就把完整的推导、实现和踩坑过程都摊开来讲一遍，适合刚学动态规划、想练背包模型或者刷 UVA 的老朋友参考。
1. 先弄明白这题到底在问什么
1.1 金字塔数的来源与直觉
所谓 square pyramidal number，描述的场景非常直观：假设你要用单位立方体小砖块搭一个四棱锥形状的金字塔，最底层是 k×k 的正方形，上面一层是 (k−1)×(k−1)，再往上是 (k−2)×(k−2)，一直到最顶层只有 1×1。那么这个四棱锥一共需要多少块砖？答案就是：
S(k) = 1² + 2² + 3² + ... + k²
这个和式就是第 k 个金字塔数的定义。前几项算一下：S(1)=1，S(2)=1+4=5，S(3)=1+4+9=14，S(4)=30，S(5)=55，S(6)=91。这个数列在整数拆分的题目里出场率不低，经常和完全背包、最少硬币问题混在一起考。
所以回到 UVa 1110，题目要做的其实就是：给你一个正整数 n，在金字塔数序列 {1,5,14,30,55,91,...} 中，允许重复选取，找到最少需要多少个金字塔数，使得它们的和恰好等于 n，并且把每个金字塔数的对应层数输出。比如 n=30，可以选 30 这一个数，答案就是 1 个，对应层数是 4；n=10，可以拆成 5+5，答案是 2 个，对应两个层数都是 2；也可以拆成 1+14 这样的非法组合，因为和不是 10，所以不考虑。注意这里“金字塔数”本身是允许重复用的，因为两个三层金字塔叠加，单位砖块总数确实是 14+14，没有问题。
1.2 数学公式推导与打表范围
谁都不会想在程序里真的用循环去计算 1²+2²+...+k²，那样每次枚举都多一层复杂度。好在平方和有闭式公式：
S(k) = k(k+1)(2k+1) / 6
这个公式怎么来的？最经典的做法是用差分法。考虑恒等式：
(k+1)³ − k³ = 3k² + 3k + 1
把 k=1 到 k=n 的这 n 个等式全部加起来，左边会错位相消，最后得到：
(n+1)³ − 1 = 3(1²+2²+...+n²) + 3(1+2+...+n) + n
其中 1+2+...+n = n(n+1)/2，代入整理就能解出平方和公式。这个过程我自己当年推导过一遍，之后再遇到类似的立方和、三角数公式都知道用什么套路去拆，建议你也亲手推一次，比死记公式有用。
有了公式，打表就简单了。k 从 1 开始往上递增，S(k) 的增长速度是 O(k³)，因为最高次项是 (2k³)/6 = k³/3。所以如果 n 的上限是 10^6，那么 k 最大只需要到 (3n)^(1/3) 这个量级，实际上 130 到 140 左右就超过了。整个物品数量 m 非常小，这让后面的动态规划非常舒服。
2. 问题建模：一眼看穿完全背包
2.1 物品、容量、价值三个要素
把原题翻译成背包语言，你会发现它简直是为完全背包量身定做的。一共有 m 个“物品”，第 k 个物品的重量是 S(k)，也就是第 k 个金字塔数；每个物品的价值是 1，也就是“使用了 1 个金字塔”；背包的容量是 n，也就是题目给出的目标总和。每种物品可以取无限次，这就是完全背包的典型特征。
定义 dp[i] 表示凑出总和 i 所需的最少金字塔数个数，初始化 dp[0]=0，其余 dp[i]=正无穷大。然后对每个金字塔数 p 做一次状态转移：
dp[i] = min(dp[i], dp[i−p] + 1)
这里最关键的是循环顺序。如果写成从大到小枚举容量，那就是 01 背包，每个金字塔数只能用一次；但本题允许重复使用同一个金字塔数，所以容量 i 必须从小到大正序遍历。正序时，dp[i−p] 可能已经在当前这个物品的轮次里被更新过，也就意味着 p 被用了多次，这正是我们想要的多重选择效果。很多初学者在这里翻车，把正序写反，结果样例能过，隐藏数据一上就崩，因为金字塔数重复取用的需求被错误地禁掉了。
2.2 为什么不能直接贪心
拿到这种题，第一反应基本都是：每次选不超过 n 的最大金字塔数，然后对剩余部分继续选最大的。这种贪心在很多货币找零场景里是有效的，但在金字塔数这里就失效了。一个经典反例是 n=110。
金字塔数序列是 1, 5, 14, 30, 55, 91, ...。贪心算法会先选 91，剩下 19，然后选 14，剩 5，再选 5，一共 3 个数：91+14+5=110。但是最优解明明可以选 55+55=110，只需要 2 个数。你看，贪心第一步吃了最大的 91，反而堵死了更优的拆分路径。这说明这类“用最少物品凑出目标值”的问题，不能靠局部最优的直觉去解，必须老老实实用动态规划把所有可能的组合状态都覆盖到。这也是背包问题最核心的思维转变：从“按策略选”到“按状态更新”。
2.3 复杂度估算与可行性
复杂度是 O(n × m)。n 是目标值上限，m 是满足 S(k) ≤ n 的金字塔数个数。前面说了，S(k) 是三次方量级，m 大约是 (3n)^(1/3)。假设 n 最大到 10^5，m 大概是 67 个左右，计算量 6.7×10^6，轻松跑完。就算 n 拉到 10^6，m 大约 144 个，计算量 1.44×10^8，C++ 在 UVA 那种老式评测环境下稍微有点压力，但优化一下初始化、用静态数组，通常也能过。如果还想更稳，可以先离线把所有可能的查询读进来，找到最大值，只跑一次 DP 到最大值，然后直接回答每个询问，这样多组数据也不会重复计算。
3. 代码实现与路径输出
3.1 预处理金字塔数
先写一个预处理函数，把不超过上限 MAXN 的所有金字塔数存进 vector。这里有两个小细节：第一，S(k) 会随 k 增长得非常快，k 加到几百就溢出 int，所以要么用 long long 判断边界，要么在 k 还比较小的时候就停；第二，金字塔数序列是严格递增的，这为后面路径回溯时的反向查找提供了方便。
vector<int> getPyramids(int maxn) { vector<int> res; for (int k = 1; ; ++k) { long long val = 1LL * k * (k + 1) * (2 * k + 1) / 6; if (val > maxn) break; res.push_back((int)val); } return res; }3.2 完全背包与方案记录
只求最少个数的话，一个一维 dp 数组就够了。但 UVa 1110 会要求你输出具体方案，所以必须记录路径。我用的是 pre[i] 数组，含义是：凑出总和 i 时，最后放入的那个金字塔数是多少。这样从 n 开始不断回退，每次减去 pre[x] 并顺手记录下来，直到 x 变成 0，就得到了完整的选取序列。
有一个特别容易错的地方：更新 dp[i] 的条件必须是严格小于，而不是小于等于。如果用小于等于去更新，当 dp[i] 已经等于 dp[i−p]+1 时，pre[i] 可能被反复改写，导致回溯路径不稳定，但最终个数不受影响。为了保证输出稳定，我只在严格更优时更新路径。
void solve(int n, const vector<int>& pyra) { const int INF = 0x3f3f3f3f; vector<int> dp(n + 1, INF), pre(n + 1, -1); dp[0] = 0; for (int p : pyra) { for (int i = p; i <= n; ++i) { if (dp[i - p] + 1 < dp[i]) { dp[i] = dp[i - p] + 1; pre[i] = p; } } } // 回溯 vector<int> ans; int cur = n; while (cur > 0) { ans.push_back(pre[cur]); cur -= pre[cur]; } // ans 是逆序的，所有金字塔数的对应层数需要反向输出 }有人可能会问，为什么外层循环遍历金字塔数、内层正序遍历容量，得到的 pre 就能正确记录路径？因为完全背包的经典写法就是外层物品、内层容量正序，每个物品可以被使用任意次。你如果把内外层交换，虽然 dp 值的结果一样，但路径记录会变得很混乱，因为你无法确定每个容量点最后是由哪个物品更新的，顺序会被打乱。所以想输出方案时，老老实实保持“物品在外、容量在内”这种标准写法最安全。
3.3 完整代码模板
下面是一份能直接提交的 C++11 代码，n 的上限我按常见的 100000 处理。实际题目如果给的更大，把 MAXN 调大即可。
#include <bits/stdc++.h> using namespace std; vector<int> buildPyra(int maxn) { vector<int> v; for (int k = 1; ; ++k) { long long val = 1LL * k * (k + 1) * (2 * k + 1) / 6; if (val > maxn) break; v.push_back((int)val); } return v; } int main() { const int MAXN = 200000; vector<int> pyra = buildPyra(MAXN); int n; while (scanf("%d", &n) == 1) { const int INF = 0x3f3f3f3f; vector<int> dp(n + 1, INF), pre(n + 1, -1); dp[0] = 0; for (int p : pyra) { if (p > n) break; for (int i = p; i <= n; ++i) { if (dp[i - p] + 1 < dp[i]) { dp[i] = dp[i - p] + 1; pre[i] = p; } } } vector<int> ans; for (int cur = n; cur > 0; ) { ans.push_back(pre[cur]); cur -= pre[cur]; } printf("%d\n", (int)ans.size()); // 从后往前输出每个金字塔数对应的层数 for (int i = (int)ans.size() - 1; i >= 0; --i) { int val = ans[i]; int level = 1; // 也可以用二分，但 m 很小，线性查找足够 for (int k = 1; ; ++k) { if (1LL * k * (k + 1) * (2 * k + 1) / 6 == val) { level = k; break; } } printf("%d%c", level, i == 0 ? '\n' : ' '); } } return 0; }这段代码的核心思路就两部分：先跑完全背包求最小数量，再用 pre 数组回溯方案。输出部分我做了层数转换，因为题目关心的是“金字塔有几层”，而不是砖块总数。由于金字塔数和层数是一一对应的，你可以打表时顺便用一个 map 存映射，省去每次查找的开销，但 m 很小，线性查找也完全没问题。
4. 常见坑点与调试实录
4.1 INF 的选择与初始化
用 0x3f3f3f3f 作为正无穷是个好习惯，因为两个 INF 相加也不会溢出 int。如果你手贱用 0x7fffffff，在 dp[i−p]+1 这一步直接变成负数，后面的 min 判断全乱，整个 DP 就废了。我早期就犯过这个低级错误，调试半天以为算法写错了，最后发现是无穷大值设得太大，加法溢出变成负数，导致更新条件永远不成立。另一个细节是 vector 初始化时用 dp.assign(n+1, INF)，别在循环里手动 memset 一个动态数组，容易越界。如果你用固定数组，memset(dp, 0x3f, sizeof(dp)) 也是可以的，但要注意 dp[0] 要单独置 0。
4.2 循环顺序真的是重灾区
我见过太多次这个错误：外层循环枚举容量 i，内层循环枚举金字塔数 p，然后容量正序，结果 dp 值算出来一样，但仔细推几个状态就会发现，同一轮更新中可能同时加入多个不同物品，这虽然不会改变最小值，却会破坏 pre 数组的语义。因为 pre 应该记录的是“最后一个选择”，如果更新顺序乱了，你没法保证 pre 指向的确实是最后放入的那个物品，回溯出来的方案可能是错的。
所以在输出方案的题目里，请一定写成：
for 每个金字塔数 p: for 容量 i 从 p 到 n: 更新 dp[i]这样当容量 i 第一次达到可以通过多个 p 组合得到时，内层循环的更新顺序决定了 pre[i] 是谁，但回溯时我们每次减掉 pre[cur]，这个 pre 始终是“最近一次放入的物品”，逻辑上是闭环的。
4.3 多组数据与输出格式
UVA 的题大多数都喜欢多组输入直到 EOF，Pyramids 也不例外。所以读入要用 while (scanf("%d", &n) == 1) 而不是只读一次。每组输出之间要不要空行、每行末尾要不要多余空格，这些细节一定要看清原题。我写代码时习惯用“第一个数后面带空格，最后一个数后面换行”的方式，配合一个 i==0 判断来控制，这样输出干净又不容易因为多余空格吃 Presentation Error。PE 是 UVA 上最常见的非技术性惩罚，很多人的算法明明是对的，结果输出格式查了半天。
4.4 关于“一定有解”这件事
因为金字塔数序列里有 1，所以任意正整数 n 都能用 n 个“1”凑出来，答案必然存在。这意味着你不需要写无解分支。但如果你把金字塔数序列打表时漏掉了 1，比如从 k=2 开始，那结果就完全变了，dp[1] 永远无法更新。这里也提醒一下，验证边界数据时可以先试 n=1、n=2、n=5，这些最小用例能快速暴露初始化或边界问题。
4.5 一个调戏过我的案例
我记得第一次交这道题时，本地测试 n=55，输出 1 个金字塔，层数是 5，完全没问题。但测 n=56 的时候，答案应该是 55+1，两个金字塔。我的回溯代码一开始写的是把 ans 直接按原顺序输出，结果把 1 和 5 的顺序搞反了，显示成“层数1 层数5”，看起来像先放了一个一层金字塔再放一个五层金字塔。虽然加法具有交换律，顺序本身不影响正确性，但如果题目要求按层数从小到大或者从大到小输出，漏掉 reverse 就会 WA。所以回溯完记得把 ans 反转。这个细节我在别的背包方案输出题里也反复踩过，算是背包路径输出的通病。
5. 从这道题延伸出去
5.1 背包模型识别训练
做完 UVa 1110，你其实已经掌握了一类题的标准套路：给定若干种面值的物品，每种无限量，问凑出目标值的最少数量或方案数。这个套路可以套到大量题目上，比如经典的 UVA 674 Coin Change，以及 LeetCode 上的完全平方数。完全平方数那道题和 Pyramids 几乎一模一样，只是把金字塔数序列换成了平方数序列 1,4,9,16,...。你把金字塔数换成平方数，把层数换成平方根，算法框架完全不用动，这就叫模型的泛化能力。
我在带学弟的时候经常说，刷题不是背题，而是练“把新问题映射到旧模型”的嗅觉。Pyramids 的包装是一个几何金字塔，但你撕开包装，里面有清晰的物品、容量、价值三要素，这就是背包问题的标准特征。识别出这一点，解题就完成了一半。
5.2 变体与进阶方向
如果题目改为每个金字塔数最多用一次，模型就从完全背包退化成 01 背包，循环顺序改成倒序即可；如果要求输出所有可行方案，就不能只用一个 dp 数组，而要用 dp 加回溯或者直接递归枚举；如果 n 的上限变成 10^18，m 会涨到百万级别，O(nm) 肯定不可行，那就需要利用金字塔数的增长性质做更高级的剪枝，甚至考虑贪心加局部动态规划的混合策略。
还有一个很有意思的数学方向：四平方和定理保证任意正整数可以表示为至多 4 个平方数之和，那么金字塔数有没有类似的表达定理？我知道金字塔数因为有 1 兜底，任何数当然都能表示，但“至多多少个”的问题就没有平方数那么漂亮。刷题时偶尔想想这些问题，能把算法的视野拉高不少，对竞赛思维是很好的补充。
我自己刷这道题的体会是，UVa 1110 的难度并不在算法本身，而在于你能不能顶住一层层包装，迅速抓住“最少个数 + 完全背包 + 路径输出”这三个关键词。有了 Pyramids 打底，以后再遇到类似的数论构造序列 + 背包的题目，你会条件反射般地把打表、动态规划、回溯三件套直接铺开，整个过程行云流水。这种解题肌肉记忆，才是刷老 UVA 最大的收获。
