杭电-2084 数塔

image.png

我的思路：
首先，我们根据结点在二维数组中的位置对结点进行简单的编号，例如：

image.png

从顶点出发，我们面对的第一个问题就是该往左走还是往右走。
我们假设起点为 a[ i ][ j ]，从左走 经过的结点的数字之和最大为d[ i+1 ][ j ]，往右走经过的结点的数字之和最大为d[ i+1 ][ j+1 ]

显然，
1，对于不是在底部倒数二行的结点，在没有遍历完全部数字结点的情况下，我们无法求出最大和d[ i ][ j ]，但是可以将其递归表示为

max 作用是取较大值

2，底部倒数二行结点可以直接求出d[ i ][ j ]，往左则 d[ i ][ j ] = a[ i ][ j ] + a[ i+1 ][ j ]，往右则 d[ i ][ j ] = a[ i ][ j ] + a[ i+1 ][ j+1] 同样取它们的较大值。

3，底部则直接d[ i ][ j ] = a[ i ][ j ]
不难发现情况2包括在情况1中，之所以写出来主要是想让大家知道，这是可以求出来的。

但仅是这样还不够，复杂度过高，因为 “夹在中间的结点” 被重复计算了。

image.png

实际计算了这么多的内容

image.png

可以想象，当数塔很高的时候，重复计算的量非常大。
如果数塔高度为n，则一共重复计算了个结点。

为避免重复计算，我们可以使用一个d[ i ][ j ]数组，初值赋上一个结点不可能存储的数字，在该题中结点取值范围为[0,99]，所以我们可以赋值-1

每次计算前都判断d[ i ][ j ]是否已经存在，如果已经存在则直接跳过就行了。

AC代码：

#include<stdio.h>

int a[101][101];
int d[101][101];
int n,high;

int max(int a,int b){
    if(a >= b)
        return a;
    return b;
}

int solve(int i, int j){
    if(d[i][j]==-1){
        if(i<high)
            return d[i][j] = a[i][j] + max(solve(i+1,j), solve(i+1,j+1));
        else
            return d[i][j] = a[i][j];
    }
    else
        return d[i][j];
    
}

int main(){
    scanf("%d",&n);
    for(int k=0;k<n;k++){
        scanf("%d",&high);
        for(int i=0;i<high;i++)
            for(int j=0;j<=i;j++){
                scanf("%d",&a[i][j]);
                d[i][j] = -1;    
            }
        
        printf("%d\n",solve(0,0));
    }
    return 0;
}

参考 : 《算法竞赛入门经典第二版-刘汝佳》第九章动态规划初步