1177: 三角形（动态规划）

核心：利用动态规划的思想，从下向上求解最大路径和

代码：

"""动态规划"""
T = int(input())
for i in range(T):
    n = int(input())
    dp = []
    for i in range(n):
        l1 = [int(x) for x in input().split()]
        dp.append(l1)
    for i in range(n-2, -1, -1):  # 从倒数第二行开始推
        for j in range(0, i+1):
            dp[i][j] += max(dp[i+1][j], dp[i+1][j+1])
    print(dp[0][0])