描述

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

输入

输入数据首先包括一个整数 C，表示有 C 组测试数据，每组测试数据的第一行是一个整数 N(1 <= N <= 100)，表示数塔的高度，接下来用 N 行数字表示数塔，其中第 i 行有个 i 个整数，且所有的整数均在区间 [0, 99] 内。

输出

对于每组测试数据，输出可能得到的最大和，每组测试的输出占一行。

输入样例 1 

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

输出样例 1

30

#include <stdio.h>

int max(int a,int b)
{
    return (a > b) ? a : b; //返回两个数中的最大值
}

int main() 
{
    int C;
    scanf("%d", &C); //输入测试用例个数
    while (C--)
    {
        int N;
        scanf("%d", &N); //输入网格的行数
        int arr[100][100]; //定义网格
        int dp[100][100]; //定义动态规划数组
        for (int i = 0; i < N; i++)
            for (int j = 0; j < i+1; j++)
                scanf("%d", &arr[i][j]); //输入网格的值
        for(int j=0;j<N;j++)
          dp[N-1][j]= arr[N-1][j]; //初始化最后一行
        for(int i=N-2;i>=0;i--)
            for(int j=0;j<i+1;j++)
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+arr[i][j]; //计算动态规划数组
        printf("%d\n",dp[0][0]); //输出结果
    }
        return 0;
  }