动态规划实践：数字三角形问题分析
- 数字三角形的动态规划分析
按照动态规划的求解步骤，我们一步步拆解这个问题：
1.1 最优子结构与递推方程式
首先明确状态定义：设 dp[i][j]表示从数字三角形顶部（第0行第0列）走到第i行第j列时，路径经过的数字总和的最大值（行、列索引从0开始）。
最优子结构性质：
走到第i行第j列的最优路径，必然是从它的两个“前驱位置”（第i-1行的j-1列、第i-1行的j列）的最优路径中，选总和更大的那个，再加上当前位置的数字。
递推方程式：
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
边界条件：
三角形顶部只有1个元素：dp[0][0] = triangle[0][0]
每行的边界列（避免越界）：
当j=0（每行第1列）：dp[i][0] = dp[i-1][0] + triangle[i][0]（只能从正上方走下来）
当j=i（每行最后1列）：dp[i][j] = dp[i-1][j-1] + triangle[i][j]（只能从左上方走下来）
1.2 填表法的细节
表的维度：用n×n的二维数组（n是三角形的行数），第i行仅用到前i+1列（其余位置可忽略）。
填表范围：从第1行（i=1）到第n-1行，每行的列j从0到i。
填表顺序：按“行从上到下、每行从左到右”填写——因为计算第i行的dp值，仅依赖第i-1行的结果。
原问题的最优值：三角形的“底”是第n-1行，最优值是第n-1行所有dp[n-1][j]（j从0到n-1）中的最大值。
比如输入样例中n=5，最后一行的dp值是24、30、27、26、24，最大值30就是最终答案。
1.3 时间与空间复杂度
时间复杂度：需要遍历每个可到达的位置（第i行有i+1个位置），总操作数为 1+2+3+…+n = \frac{n(n+1)}{2}，因此时间复杂度是 O(n²)。
空间复杂度：
用二维数组存储时，空间复杂度是 O(n²)；
若优化为一维数组（用当前行覆盖上一行结果），空间复杂度可降为 O(n)。
- 对动态规划算法的理解和体会
做完数字三角形的分析，我对动态规划的认知更具体了：
核心是“化繁为简+复用子解”：把“从顶到底的最大路径和”大问题，拆成“走到每个位置的最大和”小问题，且小问题的解可以复用，避免了暴力递归的“重复计算”痛点。
“最优子结构”是前提：大问题的最优解必须能由子问题的最优解推导而来（比如数字三角形中，每个位置的最优路径依赖前驱的最优路径）。
状态定义是“灵魂”：合理的状态定义（比如本次的dp[i][j]）能自然推导出转移方程；如果状态定义不合理，后续步骤会很难推进。
不过动态规划不是万能的——得先判断问题是否满足“重叠子问题”和“最优子结构”，否则强行使用反而会绕远