单测试点时限: 2.0 秒

内存限制: 256 MB

有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的数字和最小。

9

12 15

10 6 8

2 18 9 5

19 7 10 4 16

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

输出
对于每个测试实例，输出路径上的数字和最小值。

样例
input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
这个题目的数据只是为了方便大家看，读入的时候不需考虑多余的空格和换行
output
17

题目大意：

从数塔上层走到最底层，每次可以选择向左或向右，求路径之和最小值。

题目解析：

数塔，标准的动态规划题，用dp[i][j]表示从顶层到i,j这个位置路径之和的最小值，则初始化dp[1][1]=A[1][1]，每次向下判断。状态转移方程：

dp[i+1][j]=min(dp[i][j]+A[i+1][j],dp[i+1][j]);
dp[i+1][j+1]=min(dp[i][j]+A[i+1][j+1],dp[i+1][j+1]);

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 105
int A[MAXN][MAXN];
int dp[MAXN][MAXN];
int main() {
	int T,m,n;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		fill(dp[0],dp[0]+MAXN*MAXN,999999999);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=i;j++)
				scanf("%d",&A[i][j]);
		dp[1][1]=A[1][1];
		for(int i=1;i<n;i++){
			for(int j=1;j<=i;j++){
				dp[i+1][j]=min(dp[i][j]+A[i+1][j],dp[i+1][j]);
				dp[i+1][j+1]=min(dp[i][j]+A[i+1][j+1],dp[i+1][j+1]);
			}
		}
		int minres=999999999;
		for(int i=1;i<=n;i++){
			if(dp[n][i]<minres)
				minres=dp[n][i];
		}
		cout<<minres<<endl;
	}
	return 0;
}