数字三角形（dp）_三角dp

题目

输入样例：

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

输出样例：
30

本题中，由于n的范围上限为500，采用暴力解决将超时，因此选用dp法。

由题目可知，每个数都只能与它左下方或右下方的结点进行累加。当采用正序dp时，三角形腰上的结点（即边界结点）需考虑不存在左上角或右上角的边界情况，将增加考虑情况，因此倒序dp为最优解。

倒序dp：

#include<iostream>
using namespace std;

const int N=505;
int f[N][N];
int n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }
    }

    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
        }
    }
    cout<<f[1][1]<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23