|
水的数字三角形，DP转移方程： dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+num[i][j].(j>1);
dp[i][j]=dp[i-1][j]+num[i][j] (j==1)
在最后一行dp[N][i]中找最大即可。
代码：
#include
#include
#include
using namespace std;
const int MAXN=351;
int dp[MAXN][MAXN];
int num[MAXN][MAXN];
int main()
{
int N;
while(cin>>N)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=N;i++){
for(int j=1;j<=i;j++)
cin>>num[i][j];
}
dp[1][1]=num[1][1];
for(int i=2;i<=N;i++){
for(int j=1;j<=i;j++){
if(j==1) dp[i][j]=dp[i-1][j]+num[i][j];
else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+num[i][j];
}
}
int ans=0;
for(int i=1;i<=N;i++) ans=max(ans,dp[N][i]);
cout<
|