可以说是最简单的DP问题了。
从底向上计算,然后顶部就是权值之和最大的路径了。
#include<stdio.h> #include<stdlib.h> #include<string.h> int tree[101][101]; int maxn(int a,int b) { return a>b?a:b; } int main() { int n,t; int i,k; scanf("%d",&n); while(n--) { memset(tree,0,sizeof(tree)); scanf("%d",&t); for(i=1;i<=t;i++) { for(k=1;k<=i;k++) { scanf("%d",&tree[i][k]); } } for(i=t;i>=2;i--) { for(k=1;k<i;k++) { tree[i-1][k]=maxn(tree[i][k],tree[i][k+1])+tree[i-1][k]; } } printf("%d\n",tree[1][1]); } return 0; }