1. 题目背景与需求分析
数字金字塔是东华大学OJ平台上的一道经典算法练习题（题号72），也是动态规划和深度优先搜索算法的典型教学案例。题目给出一个由数字组成的金字塔结构，要求从顶层到底层找到一条路径，使得路径上数字的总和最大。
金字塔结构示例：
5 3 6 7 2 91.1 问题建模
我们需要将金字塔结构转化为可计算的数据模型。常见存储方式包括：
- 二维数组表示：
dp[i][j]表示第i层第j个数字 - 邻接表表示：适合图论解法
- 树形结构表示：便于递归处理
对于这个规模的问题（通常金字塔层数n≤100），二维数组是最直观的存储方式。数组下标从0开始还是从1开始需要根据编程习惯确定，本文示例采用数学坐标系（第1层第1个元素为dp[1][1]）。
2. 深度优先搜索（DFS）解法
2.1 算法思路
DFS解法采用递归思想，从金字塔顶端出发，每次可以选择向左下或右下的数字移动，直到到达最底层。所有路径中取最大值。
递归公式：
dfs(i,j) = dp[i][j] + max(dfs(i+1,j), dfs(i+1,j+1))其中i表示当前层数，j表示当前层中的位置索引。
2.2 代码实现（C++）
#include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; int dp[MAXN][MAXN]; int n; int dfs(int i, int j) { if (i == n) return dp[i][j]; return dp[i][j] + max(dfs(i+1, j), dfs(i+1, j+1)); } int main() { cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) cin >> dp[i][j]; cout << dfs(1, 1) << endl; return 0; }2.3 算法分析
时间复杂度：O(2^n) —— 每个节点有两个分支，形成二叉树结构 空间复杂度：O(n) —— 递归栈深度
注意：纯DFS解法在n>30时就会超时，需要配合记忆化优化
3. 动态规划（DP）解法
3.1 算法思路
动态规划采用自底向上的递推方式，从金字塔底层开始计算每个位置到底层的最大路径和，逐步推导到顶层。
状态转移方程：
dp[i][j] += max(dp[i+1][j], dp[i+1][j+1])3.2 代码实现（C++）
#include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; int dp[MAXN][MAXN]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) cin >> dp[i][j]; for (int i = n-1; i >= 1; --i) for (int j = 1; j <= i; ++j) dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]); cout << dp[1][1] << endl; return 0; }3.3 算法优化
空间优化版（滚动数组）：
int dp[2][MAXN]; // 使用 dp[i%2] 和 dp[(i+1)%2] 交替更新3.4 算法分析
时间复杂度：O(n^2) —— 双层循环 空间复杂度：O(n^2) 或 O(n)（优化后）
4. 两种解法的对比与实践建议
4.1 性能对比表
| 指标 | DFS解法 | DP解法 |
|---|---|---|
| 时间复杂度 | O(2^n) | O(n^2) |
| 空间复杂度 | O(n) | O(n^2)/O(n) |
| 适用场景 | 教学演示 | 实际应用 |
| 编码难度 | 较简单 | 中等 |
| 扩展性 | 较差 | 较好 |
4.2 选择建议
- 教学目的：建议先实现DFS解法，理解问题本质
- 竞赛场景：必须使用DP解法
- 数据规模：
- n≤20：两种方法均可
- 20<n≤1000：必须用DP
- n>1000：考虑空间优化版DP
4.3 常见错误排查
- 数组越界：确保循环边界正确（特别是j≤i）
- 初始化问题：DP解法需要从n-1层开始递推
- 输入格式：注意金字塔的输入方式（逐行输入）
- 最大和溢出：使用long long代替int处理大数据
5. 算法扩展与变种
5.1 输出具体路径
在DP解法中增加路径记录：
int path[MAXN]; // 记录路径选择 // 在状态转移时记录选择 if (dp[i+1][j] > dp[i+1][j+1]) { dp[i][j] += dp[i+1][j]; path[i] = j; } else { dp[i][j] += dp[i+1][j+1]; path[i] = j+1; }5.2 三维金字塔问题
当每个位置有三个选择（左、中、右）时：
dp[i][j] += max({dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]});5.3 最小路径和问题
将max改为min即可求最小路径和：
dp[i][j] += min(dp[i+1][j], dp[i+1][j+1]);6. 实际应用场景
- 游戏AI路径规划：如RPG游戏中的最优收益路线
- 投资决策：分层决策模型中的最优选择
- 资源分配：多层资源分配的最大效益问题
- 神经网络：某些网络结构的正向传播计算
7. 编程技巧与优化
- 输入优化：使用快速读取方法处理大规模输入
ios::sync_with_stdio(false); cin.tie(0); - 边界处理：在数组周围填充0避免边界判断
for (int i = 0; i <= n+1; ++i) for (int j = 0; j <= i+1; ++j) dp[i][j] = -INF; // 初始化 - 记忆化搜索：DFS+记忆化的混合解法
int memo[MAXN][MAXN]; int dfs(int i, int j) { if (memo[i][j] != -1) return memo[i][j]; // ...其余相同 }
8. 不同语言的实现差异
8.1 Python实现特点
# DP解法 n = int(input()) dp = [list(map(int, input().split())) for _ in range(n)] for i in range(n-2, -1, -1): for j in range(i+1): dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]) print(dp[0][0])注意事项：
- Python递归深度限制（默认1000）
- 使用lru_cache实现记忆化
- 处理大数自动转为长整型
8.2 Java实现注意点
// 需要处理输入输出效率 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 数组初始化为0 int[][] dp = new int[n+2][n+2];9. 测试用例设计
有效测试用例应包括：
最小用例（n=1）：
1 5预期输出：5
常规用例：
3 1 2 3 4 5 6预期输出：10（1→3→6）
边界用例：
- 所有元素相同
- 严格递增/递减
- 包含负数
最大规模用例（n=100）：验证算法效率
10. 学习路线建议
基础阶段：
- 理解递归和递推的区别
- 掌握二维数组操作
- 熟悉基本输入输出处理
进阶阶段：
- 学习记忆化搜索技术
- 掌握滚动数组优化
- 理解状态压缩DP
扩展学习：
- 图论中的最短路径算法
- 树形DP问题
- 背包问题的变种
在实际编程练习中，建议从简单的DFS实现开始，逐步过渡到DP解法，最后尝试各种优化技巧。东华大学OJ平台上的这道题目是算法学习的经典案例，掌握其解法对后续学习更复杂的动态规划问题大有裨益。
