输入：
第一行 n
后面 n 行是数据
输出：所有数据的和

注意点

  1. 数塔问题是从下往上
  2. 为了方便表示，可以从dp[1][1]开始

代码

  1. #include<algorithm>
  2. #include<vector>
  3. #include<cstdio>
  4. using namespace std;
  6. const int maxn = 1000;
  7. int fn[maxn][maxn], dp[maxn][maxn];
  9. int main(){
  10.     int n;
  11.     scanf("%d", &n);
  12.     for(int i = 0; i < n; i++){
  13.         for(int j = 0; j <= i; j++){
  14.             scanf("%d", &fn[i][j]);
  15.         }
  16.     }
  17.     //初始化DP数组
  18.     for(int i = n - 1; i >= 0; i--){
  19.         for(int j = 0; j <= i; j++){
  20.             if(i == n - 1) dp[i][j] = fn[i][j];//最后一排等于最后一排
  21.             else{
  22.                 dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + fn[i][j];
  23.             }
  24.         }
  25.     }
  26.     printf("%d", dp[0][0]);
  27. }