這是一道動態(tài)規(guī)劃的題目

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

如果我知道第0-i層的最大值，那么第i+1層的最大值顯然了，但是這樣不怎么好處理，下面我把這個三角數(shù)陣倒著看：

4 5 2 6 5
2 7 4 4
8 1 0
3 8
7

用t[i][j]來表示這個三角數(shù)陣，那么對于第i層的數(shù)，我很清楚的知道它與第i+1層的哪個數(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;
}