这个题目,或者说这样的题目是动态规划的入门例题.这里的最优结构很明显,算法上没有什么好讲的.实现上,建议利用滚动数组以节省空间,虽然你开个二维的也未必会挤爆空间.
1 /*
2 ID: 31440461
3 LANG: C++
4 TASK: numtri
5 */
6 #include<iostream>
7 using namespace std;
8 const int MAXN=1000+10;
9 int data[2][MAXN];
10
11 int main()
12 {
13 freopen("numtri.in","r",stdin);
14 freopen("numtri.out","w",stdout);
15 int n,flg=0;
16 cin >> n;
17 for (int i=1;i<=n;++i)
18 {
19 flg=1-flg;
20 for (int j=1;j<=i;++j)
21 {
22 int x;
23 cin >> x;
24 data[flg][j]=max(data[!flg][j-1],data[!flg][j])+x;
25 }
26 }
27 int m=0;
28 for (int i=1;i<=n;++i) m=max(m,data[flg][i]);
29 cout << m << endl;
30 return 0;
31 }
32