实践报告
按照动态规划法的求解步骤分析作业题目“数字三角形”：
1.1 根据最优子结构性质，列出递归方程式，说明方程式的定义、边界条件
递归方程式：dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j])
状态定义：设 dp[i][j] 表示从三角形顶部（第 0 行第 0 列）到第 i 行第 j 列时的最优路径和（行、列均从 0 开始计数）。
边界条件：
1.第 0 行仅有 1 个元素，dp[0][0] = triangle[0][0]（起点路径和为自身）；
2.每行第 0 列元素（最左侧），仅能从上方到达，dp[i][0] = triangle[i][0] + dp[i-1][0]；
3.每行第 i 列元素（最右侧，与行号相等），仅能从左上到达，dp[i][i] = triangle[i][i] + dp[i-1][i-1]。
1.2 给出填表法中表的维度、填表范围和填表顺序。以及原问题的最优值是哪个表格元素
表的维度：二维表格 dp，维度与数字三角形一致，即 n×n（n 为三角形的行数）
填表范围：0 ≤ i < n、0 ≤ j ≤ i（第 i 行仅有 i+1 个元素，j 最大不超过 i）。
填表顺序：按行从上到下依次填充，每行内从左到右填充；先填第 0 行，再填第 1 行至第 n-1 行。
原问题最优值：第 n-1 行所有 dp[n-1][j]（0 ≤ j < n）中的最大值，即 max(dp[n-1][0], dp[n-1][1], ..., dp[n-1][n-1])。
1.3 分析该算法的时间和空间复杂度
时间复杂度：O(n²)。需填充 n×(n+1)/2 个表格元素，每个元素计算为常数时间操作。
空间复杂度： 1. 基础实现（二维表格）：O(n²)，存储完整的 n×n 动态规划表；
你对动态规划算法的理解和体会
动态规划是解决多阶段决策最优化问题的核心算法，核心思想是拆分问题为子问题，复用子问题解以规避重复计算，实现效率跃升。
其核心在于识别“最优子结构”与“重叠子问题”：前者保障原问题最优解可由子问题最优解推导，后者是制表复用的前提。
求解关键在于五步：清晰定义状态（描述问题阶段特征）、推导递归方程式（建立状态关联）、明确边界条件（终止递归）、规划填表顺序（确保子问题先解）、可选空间优化（如滚动数组压缩维度）。
动态规划平衡了时间与空间成本，相比暴力搜索效率天差地别（如数字三角形问题从 O(2^n) 降至 O(n²)）。其难点在于状态定义与子结构识别，需通过实践积累经验；空间优化则需吃透填表逻辑，避免数据覆盖错误。