【线性dp】【题解】数字三角形

一篇普通的题解。（本蒟蒻的第一篇文章😄）

算法分类

线性dp

题目描述

有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数。
图例：

从第一行的数开始，每次可以往左下或右下走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和尽量大？

输入格式：
第一行输入整数 n 表示三角形的层数。
在接下来的 n 行中，每一行表示三角形的中每一行整数，整数之间以空格隔开。

输出格式：
输出三角形从第一行的数到最后一行数所经过的数字之和的最大值。

---

样例输入：

4
1
3 2 
4 10 1
4 3 2 20

样例输出：

24

---

样例解释：
1—->2—->1—->20
1+2+1+20=24

---

数据范围与提示：
1 n 1000

解题思路

设表示从（1，1）到（i，j)路径上的数的最大和
由此可以轻松推导出转移方程：

$$\text{ (1 < i$\leq$n且1$\leq$j$\leq$n) }$$ $$f(i,j)= \begin{cases} f(i-1,j-1)+a[i][j], &\text {f(i-1,j-1) $\geq$ f(i-1,j)} \\ f(i-1,j)+a[i][j], &\text {f(i-1,j-1) < f(i-1,j)} \end{cases}$$

即：

$$f[i][j]=a[i][j]+max( f[i-1][j-1],f[i-1][j] ) \quad \text{ (1 < i$\leq$n且1$\leq$j$\leq$n) }$$

Code

(仅供参考)

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1005][1005];         //构建数字三角形 
int dp[1005][1005],maxn;   //因为是非负整数，所以maxn初始化为0 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dp[1][1]=a[1][1];       //初始化第一个点 
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];  //转移方程 
		}
	}
	for(int i=1;i<=n;i++)
	{
		maxn=max(maxn,dp[n][i]);   //因为终点不确定，所以遍历整个最后一行，找到最大路径 
	}
	printf("%d",maxn);
	return 0;
} 

链接

洛谷P1216