poj1163

这是一道动态规划的题目

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

如果我知道第0-i层的最大值，那么第i+1层的最大值显然了，但是这样不怎么好处理，下面我把这个三角数阵倒着看：

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

用t[i][j]来表示这个三角数阵，那么对于第i层的数，我很清楚的知道它与第i+1层的哪个数相加最大，即
t[i][j] += t[i+1][j] > t[i+1][j+1] ? t[i+1][j] : t[i+1][j+1]
到这里应该知道如何做了吧！

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;
}