来自CodeVS1220 数字三角形 CodeVS的天梯题目排序这里就不吐槽了，这题最后一题还以为是最难的。实际上就是一大\(H_2O\)题
题目描述 Description如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。
输入描述 Input Description第一行是数塔层数N(1<=N<=100)。
第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。
输出描述 Output Description输出最大值。
样例输入 Sample Input5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
样例输出 Sample Output86
数据范围及提示 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>
Comments | NOTHING