問題分析:用一個二維數組a[i][j]來存儲這些數字,設M[i][j]表示的是從a[i][j]開始所加和的最大值,則轉移方程可表示為:
M[i][j] = max(M[i+1][j] ,M[i+1][j+1]) + a[i][j];問題迎刃而解。
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define INPUT freopen("D:\\iotest\\in.txt", "r", stdin)
#define OUTPUT freopen("D:\\iotest\\out.txt", "a", stdout)
#define TIME printf("%.3lf s", (double)clock() / CLOCKS_PER_SEC)
#define TEST printf("this is an output test!!!")
using namespace std;
const int MAXSIZE = 1000 + 5;
int dp[MAXSIZE][MAXSIZE];
int a[MAXSIZE][MAXSIZE] = {0};
int n;
int large(int i ,int j)
{
if(dp[i][j] > 0) return dp[i][j];
else if(i == n) return dp[i][j] = a[i][j];
else{
return dp[i][j] = max(large(i+1,j), large(i+1, j+1)) + a[i][j];
}
}
int main()
{
INPUT;
OUTPUT;
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= i; ++j)
cin >> a[i][j];
memset(dp, -1, sizeof(dp));
cout << large(1, 1) << endl;
// TIME;
return 0;
}