[DP经典题]数字三角形

发布于 2017-07-13  71 次阅读


来自CodeVS1220 数字三角形 CodeVS的天梯题目排序这里就不吐槽了,这题最后一题还以为是最难的。实际上就是一大\(H_2O\)题

题目描述 Description

如图所示的数字三角形,从顶部出发,在每一结点可以选择向左走或得向右走,一直走到底层,要求找出一条路径,使路径上的值最大。

输入描述 Input Description

第一行是数塔层数N(1<=N<=100)。

第二行起,按数塔图形,有一个或多个的整数,表示该层节点的值,共有N行。

输出描述 Output Description

输出最大值。

样例输入 Sample Input

5

13

11 8

12 7 26

6 14 15 8

12 7 13 24 11

样例输出 Sample Output

86

数据范围及提示 Data Size & Hint
数字三角形
这题是我可能也是大多数人的DP入门第一题。
一个最简单的递推,自下往上不断取最大值。
方程是:
\(f(i,j)=f(i,j)+max\{f(i+1,j),f(i+1,j+1)|i<=n-1,j<=i\}\)
我的代码:
#include<cstdio>
#include<cstring>
int map[101][101],f[101][101],n;
int max(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	scanf("%d",&n);
	memset(map,0,sizeof(map));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
	{
		scanf("%d",&map[i][j]);
	}
	for(int i=n-1;i>=1;i--)
	for(int j=1;j<=i;j++)
	{
		map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
	}
	printf("%d\n",map[1][1]);
	return 0;
}
<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1">​</span>

 

 

 


等风来,不如追风去。