這個(gè)題目,或者說這樣的題目是動(dòng)態(tài)規(guī)劃的入門例題.這里的最優(yōu)結(jié)構(gòu)很明顯,算法上沒有什么好講的.實(shí)現(xiàn)上,建議利用滾動(dòng)數(shù)組以節(jié)省空間,雖然你開個(gè)二維的也未必會(huì)擠爆空間.
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