第14周_动态规划_三角形问题_作业

本次OJ评测的主要目的是检验考生对动态规划中的关于数字三角形问题的应用，主要内容如下：

1.基本模型

（1）问题描述：从三角形顶部到底部的一条路径，使路径权值和最大。

（2）递推方向：

- 自底向上（更常用）：从底层开始递推，逐步合并子问题的解。

- 自顶向下：需要处理边界条件（如左右无子节点的情况）。

（3）状态转移方程：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

2. 必须经过某一点的变种问题

（1）核心思路：强制路径经过指定点（如中点(n/2, n/2)）。

（2）处理方法：

- 权值调整法（代码中采用的方法）：将指定点的权值增加一个极大值（如1e9），确保任何经过该点的路径的总和远大于其他路径。注意：最终结果需要减去该极大值。

- 路径拆分法：将路径分为起点到指定点和 指定点到底部；再分别计算两段的最大值，再相加。

3. 动态规划的代码实现要点

- 数组初始化：底层的dp[n][j]直接赋值为输入值。

- 递推顺序：从倒数第二层开始向上递推，每层从左到右或从右到左均可。

- 数据类型选择：当权值较大时，使用long long避免溢出。