数字三角形

题目链接：https://www.acwing.com/problem/content/900/

题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
输出最大价值。

输入描述

第一行包含整数 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

分析

约定

记第i行第j列的数为a[i][j]

状态表示

f(i,j)表示从起点出发到达第i行第j列的路径数字最大和

状态划分

对于f(i,j),存在两大种情况：

• 从左上方来
• 从右上方来

状态转移方程

对应状态划分，我们便可以得到相应的状态转移方程：
f(i,j)=max(f(i-1,j),f(i-1,j-1))+a[i][j]

边界处理

我们将f[i][j]的求解过程看作是填一张二维表的过程，求解任一f[i][j],我们需要其正上方和左上方的数据。
结合a[i][j]可以是负数，我们应将边界的f[i][j]初始化为负无穷，以应对实际只存在一条到达路径的情况。(指每一行最左侧和最右侧的数)
同时，我们再将f[1][1]初始化为a[1][1]，就能妥善处理好边界问题。

优化

由于求解过程只需要上一行的数据，我们可以采用滚动数组的思想，将f[i][j]改为一维，注意对列循环时要从后往前，防止覆盖需要用到的上一行数据。(仅给出优化后的AC代码)

AC代码

---

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 501;
const int INF = 1e9;

int n;
int a[N][N];
int f[N];

int main()
{
	cin >> n;
	for (int i = 0; i <= n; i++)
		f[i] = -INF;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			cin >> a[i][j];

	f[1] = a[1][1];
	for (int i = 2; i <= n; i++)
	{
		for (int j = i; j >= 1; j--)
		{
			f[j] = max(f[j] + a[i][j], f[j - 1] + a[i][j]);
		}
	}
	int res = -INF;
	for (int i = 1; i <= n; i++)
		res = max(res, f[i]);
	cout << res << endl;
	return 0;
}