設從頂點走到第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
成成 閱讀(405)
評論(0) 編輯 收藏 引用 所屬分類:
算法習題