总时间限制: 1000ms 内存限制: 65536kB

描述

                7
              3   8
            8   1   0
        2   7   4   4
    4   5   2   6   5
            (Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

输入

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but ≤ 100. The numbers in the triangle, all integers, are between 0 and 99.

输出

Your program is to write to standard output. The highest sum is written as an integer.

样例输入

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

样例输出

30

思路

初始解法

用二维数组存放数字三角形.
D(r, j): 第r行第j个数字(r, j从1开始计数)
MaxSum(r, j): 从D(r, j)到底边的各个路径中, 最佳路径的数字之和.

问题: 求MaxSum(1, 1)

这是典型的递归问题:
从D(r, j)出发, 下一步只能走 D(r+1, j) 或 D(r+1, j+1). 故对于N行三角形来说:

if( r == N )
    MaxSum(r, j) = D(r, j);
else 
    MaxSum(r, j) = Max( MaxSum(r+1, j), MaxSum(r+1, j+1) ) + D(r, j);

有了上面的递归式子, 我们可以写出初始的解法:

// Using C99 Standard
#include <stdio.h>
#define MAX     100
int triangle[MAX][MAX];
int number;
int MaxSum(int i, int j) {
    if( i == number )
        return triangle[i][j];
    int x = MaxSum(i+1, j);
    int y = MaxSum(i+1, j+1);
    int maxBetweenXY = x > y ? x : y;
    return (maxBetweenXY + triangle[i][j]);
}
int main() {
    scanf("%d", &number);
    for(int i = 1; i <= number; i++) {
        for(int j = 1; j <= i; j++) {
            scanf("%d", &triangle[i][j]);
        }
    }
    printf("%d\n", MaxSum(1, 1));
    return 0;
}

代码结果是对的, 但是POJ不通过, 原因是超时了.

该算法包含了很多重复计算:

1. 第一行调用了1次MaxSum
2. 第二行调用了2次MaxSum
3. 第三行调用了4次MaxSum
4. 第四行调用了8次MaxSum
5. 第五行调用了16次MaxSum

这时间复杂度是 2 , 对于比较大的测试点, 肯定超时.

我们怎么改进?

每算一次MaxSum就保存起来, 下次要算的时候就直接拿出来用. 这样的时间复杂度是O(n), 因为三角形数字总数是: n(n+1) / 2.

记忆递归型动归程序

// Using C99 Standard
#include <stdio.h>
#define MAX     100
int triangle[MAX][MAX];
int mysum[MAX][MAX];
int number;
int MaxSum(int i, int j) {
    if( mysum[i][j] != -1 )
        return mysum[i][j];
    if( i == number )
        mysum[i][j] = triangle[i][j];
    int x = MaxSum(i+1, j);
    int y = MaxSum(i+1, j+1);
    int maxBetweenXY = x > y ? x : y;
    mysum[i][j] = maxBetweenXY + triangle[i][j];
    return mysum[i][j];
}
int main() {
    scanf("%d", &number);
    for(int i = 1; i <= number; i++) {
        for(int j = 1; j <= i; j++) {
            scanf("%d", &triangle[i][j]);
            mysum[i][j] = -1;
        }
    }
    printf("%d\n", MaxSum(1, 1));
    return 0;
}

转递归为递推

我们从底层往上算，算到D(1, 1)。由于底层的每个元素到底边最大距离就是它自己，这是我们已知的。顶层D(1, 1)到底边的最大距离是未知的，由已知推出未知，是谓递推。
递推公式如下：

程序代码如下：

// Using C99 Standard
#include <stdio.h>
#define MAX     100
int triangle[MAX][MAX];
int mysum[MAX][MAX];
int number;
int main() {
    scanf("%d", &number);
    for(int i = 1; i <= number; i++) {
        for(int j = 1; j <= i; j++) {
            scanf("%d", &triangle[i][j]);
        }
    }
    for(int j = 1; j <= number; j++)
        mysum[number][j] = triangle[number][j];
    for(int i = number; i > 1; i--) {
        for(int j = 1; j < i; j++) {
            if(mysum[i][j] > mysum[i][j+1])
                mysum[i-1][j] = mysum[i][j] + triangle[i-1][j];
            else
                mysum[i-1][j] = mysum[i][j+1] + triangle[i-1][j];
        }
    }
    printf("%d\n", mysum[1][1]);
    return 0;
}