设从顶点走到第i层第j个元素的路径和最大值为maxsum[i-1][j-1]
则到第i+1层第j个元素的路径和最大值为max{maxsum[i-1][j-1]+a[i][j],maxsum[i-1][j]+a[i][j]}
而初始条件为maxsum[0] = a[0][0];且maxsum[i][0] = a[0][0]+a[1][0]+...+a[i-1][0]
#include<iostream>
using namespace std;
int main()
{
int input[100][100],maxsum[100][100],row,i,j,maxval;
cin>>row;
memset(input,0,sizeof(int)*10000);
for(i=0; i<row; i++)
{
for(j=0;j<=i;j++)
{
cin>>input[i][j];
}
}
memset(maxsum,0,sizeof(int)*10000);
maxsum[0][0] = input[0][0];
for(i=1;i<row;i++)
{
maxsum[i][0] = maxsum[i-1][0] + input[i][0];
for(j=1;j<=i;j++)
{
if(maxsum[i-1][j-1]>maxsum[i-1][j])
{
maxsum[i][j] = maxsum[i-1][j-1] + input[i][j];
}
else
{
maxsum[i][j] = maxsum[i-1][j] + input[i][j];
}
}
}
maxval = 0;
for(i=0;i<row;i++)
{
if(maxval<maxsum[row-1][i])
{
maxval = maxsum[row-1][i];
}
}
cout<<maxval<<endl;
return 0;
}
posted on 2011-08-19 17:33
成成 阅读(370)
评论(0) 编辑 收藏 引用 所属分类:
算法习题