线性DP问题（例题）

目录结构与内容概述

一、数字三角形问题

二、最长递增子序列分析

三、最长公共子序列研究

---

一、数字三角形问题解析

题目：

如下图所示，存在一个数字三角形，从最顶端开始，每个节点均可选择向左下方或右下方移动，直至抵达最底层。目标是寻找一条路径，使得该路径上所有数字的总和达到最大值。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输入格式：

输入的第一行是一个整数 n，用于表示数字三角形的总层数。随后的 n 行中，每一行均包含多个整数，其中第 i 行所对应的整数序列即为数字三角形第 i 层的具体数值。

输出格式：

输出一个整数，用以表征路径中数字总和的最大值。

数据范围界定

1≤n≤500，−10000≤三角形内的整数≤10000

输入样例解析

【

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出样例

30

题解：

这是一道典型的线性动态规划问题；

其解题思路为自下而上进行计算，其中f[ i ][ j ]用于记录从最底层出发，到达第i行第j个位置的所有路径中所能获得的最大值；