ACM数塔出错了，朋友们帮忙看看

来源：百度知道 编辑：UC知道 时间：2024/09/28 12:15:42
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

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

已经告诉你了，这是个DP的题目，你能AC吗?
Input
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

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

Sample Output
30

我的算法
#include <stdio.h>
void main()
{
int C, N, a[103][103], i = 1, j = 1, m, L, T;

scanf("%d", &C);

while(C--)
{
scanf("%d", &N);
L = N;

while(L--)
{
m = i;
while(m--)
{
scanf("%d", &a[i][j]);
j++;

}
j = 1;
i++;
}

L = N;

while(--L)
{
while(j != N)
{
if(a[N][j] > a[N][j + 1]

你的代码真个性…… 都不用for的， 而且变量用大写字母…… 很特别

代码里面就一个错，i,j,的赋值为1应该写在循环里面。相信你一想就懂了。正确的代码如下：

#include <stdio.h>
void main()
{
int C, N, a[103][103], i = 1, j = 1, m, L, T;
scanf("%d", &C);
while(C--)
{
i = 1, j = 1; //就加了这一行，就对了
scanf("%d", &N);
L = N;
while(L--)
{
m = i;
while(m--)
{
scanf("%d", &a[i][j]);
j++;
}
j = 1;
i++;
}
L = N;
while(--L)
{
while(j != N)
{
if(a[N][j] > a[N][j + 1])
T = a[N - 1][j] + a[N][j];
else
T = a[N - 1][j] + a[N][j + 1];
a[N - 1][j] = T;
j++;
}
N--;
j = 1;
}
printf("%d\n", a[1][1]);
}
}