动态规划法求解步骤
（1）状态定义：设 dp[i][j] 表示从第 i 行第 j 列元素出发，到达三角形底部的最大路径和。该定义精准捕捉了子问题的核心：每个位置的最优解仅依赖其下方的子问题结果。
（2）递归方程式推导：由于从第 i 行第 j 列仅能移动到第 i+1 行第 j 列或第 i+1 行第 j+1 列，因此当前位置的最大路径和 = 当前数字 + 下方两个位置的最大路径和的较大值，即：dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])
（3）边界条件：当到达最后一行（i = n-1）时，没有后续移动路径，路径和即为元素自身，因此边界条件为：dp[n-1][j] = triangle[n-1][j] 。
填表法
（1）填表范围：
行范围：从第 n-2 行向上填充至第 0 行（最后一行已由边界条件直接赋值，无需计算）；
列范围：对于每一行 i，填充 0≤j≤i 的有效列（与三角形每行的列数匹配）。
（2）填表顺序：由于 dp[i][j] 依赖下一行的 dp[i+1][j] 和 dp[i+1][j+1]，因此填表顺序必须为自底向上：先填充最后一行（i = n-1）：直接按边界条件赋值 dp[n-1][j] = triangle[n-1][j]，从第 n-2 行开始，向上依次填充至第 0 行，每行内部可从左到右或从右到左填充。
（3）原问题的最优值：原问题要求从顶部（第 0 行第 0 列）出发的最大路径和，而 dp[0][0] 恰好表示从顶部出发到达底部的最大路径和，因此原问题的最优值为表格中的 dp[0][0]。
算法复杂度分析
（1）时间复杂度：表格中共有 1+2+...+n = n (n+1)/2 个有效元素，每个元素的计算仅需 1 次加法和 1 次比较（O (1) 操作），因此总时间复杂度为 O(n²)，相较于朴素递归的 O (2ⁿ) 大幅提升效率。
（2）空间复杂度：基础实现：使用 n×n 的二维数组存储所有子问题解，空间复杂度为 O(n²)；
对动态规划算法的理解和体会：
（1）动态规划的核心本质：动态规划是一种针对 “具有重叠子问题和最优子结构” 的复杂问题的高效求解方法，核心思想可概括为 “存储子问题最优解，避免重复计算”。在数字三角形中，不同路径可能经过同一位置，若采用暴力搜索会重复计算该位置的路径和，而动态规划通过表格存储子问题结果，将 “重复计算” 转化为 “查表调用”，实现了效率的指数级提升。
（2）动态规划的两大关键要素：
最优子结构：这是动态规划能够成立的基础。问题的全局最优解可由子问题的最优解推导得出（如数字三角形中，父节点的最大路径和依赖子节点的最优结果），无需重新探索所有可能性。
重叠子问题：复杂问题的解包含大量重复的子问题（如数字三角形中多个路径共享中间节点），这是动态规划 “以空间换时间” 策略的前提 —— 若子问题无重叠，存储结果反而会增加额外开销。
（3）实践解题的核心步骤：求解动态规划问题的关键在于 “状态定义” 和 “转移方程推导”：状态定义需精准捕捉子问题的核心信息（如本次定义 dp[i][j] 为 “从当前位置到底部的最大路径和”，直接决定了自底向上的解题思路），转移方程需清晰描述子问题间的依赖关系，同时必须补充边界条件（否则会出现计算逻辑断裂）。空间优化是进阶技巧，需根据子问题的依赖范围（如仅依赖相邻行）合理简化存储结构，体现了动态规划的灵活性。
