這是一道動(dòng)態(tài)規(guī)劃的題目
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
如果我知道第0-i層的最大值澜躺，那么第i+1層的最大值顯然了，但是這樣不怎么好處理抒蚜，下面我把這個(gè)三角數(shù)陣倒著看：
4 5 2 6 5
2 7 4 4
8 1 0
3 8
7
用t[i][j]來表示這個(gè)三角數(shù)陣掘鄙，那么對于第i層的數(shù)，我很清楚的知道它與第i+1層的哪個(gè)數(shù)相加最大嗡髓，即
t[i][j] += t[i+1][j] > t[i+1][j+1] ? t[i+1][j] : t[i+1][j+1]
到這里應(yīng)該知道如何做了吧通铲！
AC
#include<iostream>
using namespace std;
int main(){
int n,i,j;
cin>>n;
int t[100][100];
for( i = 0; i < n; i++){
for(j = 0; j <= i; j++){
cin>>t[i][j];
}
}
for(i = n-2; i >= 0; i--){
for(j = 0; j <= i; j++){
t[i][j] += t[i+1][j] > t[i+1][j+1] ? t[i+1][j] : t[i+1][j+1];
}
}
cout<<t[0][0];
return 0;
}
