1. 实践报告
1.1 最优子结构性质与递归方程式
定义状态：
- 令 \(f(i,j)\) 表示从第 \(i\) 行第 \(j\) 列出发，走到第 \(n\) 行，能得到的最大路径和。
最优子结构：
- 从位置 \((i,j)\) 只能向下走左下 \((i+1,j)\) 或右下 \((i+1,j+1)\)，所以有递归方程式：
textf(i,j) = dp[i][j] + max( f(i+1,j), f(i+1,j+1) )
边界条件：
- 当 \(i == n\) 时，无法再向下走，所以：\(textf(n,j) = dp[n][j] (j = 1,2,...,n)\)
1.2 填表法（自底向上 DP）
我采用的是从下往上填表的做法。
表的维度：
- 二维数组 \(dp[n+1][n+1]\)，实际使用 \(dp[1...n][1...n]\)
填表范围和顺序：
-
初始：\(dp[i][j]\) 先读入三角形的原始数值（第 \(i\) 行第 \(j\) 个数）
填表从下往上、从左到右（或右到左都可）进行. -
外层循环：\(i\) 从 \(n-1\) 递减到 \(1\)（即从倒数第二行倒着往上填）
-
内层循环：\(j\) 从 \(1\) 到 \(i\)（当前行有 \(i\) 个位置）
-
填写内容：\(dp[i][j] += max(dp[i+1][j], dp[i+1][j+1])\)（把下面两个子节点的最大值加到当前格子上）
原问题的最优值：
- 填完表后，\(dp[1][1]\) 就是从顶到底的最大路径和。这正是代码里最后输出 \(dp[1][1]\) 的原因。
1.3 时间与空间复杂度分析
时间复杂度：
- 输入部分：\(O(n²)\)（总共有 \(1+2+...+n = n(n+1)/2\) 个数）
填表部分：外层循环 \(n-1\) 次，内层第 \(i\) 行最多循环 \(i\) 次，总共仍是 \(∑_{i=2}^{n} (i-1) = O(n²)\)
总体：\(O(n²)\)
空间复杂度：
- 使用了 \(dp[101][101]\) 二维数组，实际需要 \(n×n\) 的空间
所以空间复杂度：\(O(n²)\)
2. 对动态规划算法的理解和体会
动态规划训练的是“把复杂问题结构化”的能力。每次成功解决一道 DP 题，都会强化一种思维：再难的问题也可以被拆成有限的、可管理的状态。只要状态定义得当，转移逻辑严谨，答案往往自然浮现。这种“化繁为简、稳扎稳打”的感觉，是我持续喜欢动态规划的根本原因。
总的来说，动态规划不是某种“技巧合集”，而是一种系统化的、最优化的数学思维方式。掌握它，不仅能大幅提升解决问题的能力，更能在面对复杂系统时保持冷静与条理。