/*
给定一个由n行数字组成的数字三角形如下图所示。
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和
对于给定的由n行数字组成的数字三角形，
编程计算从三角形的顶至底的路径经过的数字和的最大值
*/
#include <stdio.h>
#include <string.h>
const int MAXN = 100 + 10;
int a[MAXN][MAXN],d[MAXN][MAXN];
int n;
inline int max(int a,int b) { return a > b ? a : b;}
int dfs(int i,int j)
{
if (d[i][j] >= 0) return d[i][j];
return d[i][j] = a[i][j] + (i == n ? 0 : max(dfs(i+1,j),dfs(i+1,j+1)));
}
int main()
{
int i;
int j;
freopen("1.txt","r",stdin);
while (scanf("%d",&n) != EOF)
{
memset(d,-1,sizeof(d));
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= i; ++j)
scanf("%d",&a[i][j]);
}
printf("%d\n",dfs(1,1));
}
return 0;
}
#include <stdio.h>
const int MAXN = 100 + 10;
int a[MAXN][MAXN],d[MAXN][MAXN];
int n;
inline int max(int a, int b) { return a > b ? a : b; }
int main()
{
int i,j;
freopen("1.txt","r",stdin);
while (scanf("%d",&n) != EOF)
{
for (i = 1; i <= n; ++i)
for (j = 1; j <= i; ++j)
scanf("%d",&a[i][j]);
for (j = 1; j <= n; j++) d[n][j] = a[n][j];
for (i = n - 1; i >= 1; i--)
for (j = 1; j <= i; j++)
d[i][j] = a[i][j] + max(d[i+1][j],d[i+1][j+1]);
printf("%d\n",d[1][1]);
}
return 0;
}
posted on 2011-10-08 01:24
nk_ysg 阅读(826)
评论(0) 编辑 收藏 引用 所属分类:
算法