數字三角形（動态規劃）
問題描述
（圖３.１－１）示出了一個數字三角形。 請編一個程式計算從頂至底的某處的一條路
徑，使該路徑所經過的數字的總和最大。
●每一步可沿左斜線向下或右斜線向下走；
●1＜三角形行數≤100；
●三角形中的數字為整數0，1，…99；
.
（圖３.１－１）
輸入格式
檔案中首先讀到的是三角形的行數。
接下來描述整個三角形
輸出格式
最大總和（整數）
樣例輸入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
樣例輸出
30
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 105
using namespace std;
int main(){
int n,a[maxn][maxn],sum=0;
memset(a,0,sizeof(a));
cin>>n;
//i從1開始，便于确立邊界
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
//a[i][j]每次都将上一步的結果累加進來
a[i][j]+=max(a[i-1][j],a[i-1][j-1]);
//比較目前層可出發的兩個結點的大小
if(sum<a[i][j]){
sum=a[i][j];
}
}
}
cout<<sum;
return 0;
}
解決思想：
動态規劃最優子結構性質——每次選擇目前點出發可得到的最大子和，由局部最優獲得全局最優。