/*
給定一個由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 閱讀(858)
評論(0) 編輯 收藏 引用 所屬分類:
算法