数字三角形

问题

n 行数字组成的数字三角形，例如下图：

找出一条从三角形的顶到底的路径，使路径经过的数字的和最大。 只需计算出和，不需要指明具体路径

例如上图的一个可能解，如下图：

最终解为 29

思路

为了方便解释与实现，将数字三角形放入一个矩阵，如下图：

数字三角形用 dt[row][col] 来表示，比如 dt[1][1] = 6
最大路径和用 mp[row][col] 来表示， 比如 mp[1][1] 表示从数字三角形顶点到 dt[1][1] 这个点的最大路径和

很容易就能得到一个递归规律：

• 当 col = 0 时，mp[row][col] = dt[row][col] + mp[row-1][col]
• 当 row = col 时，mp[row][col] = dt[row][col] + mp[row-1][col-1]
• 其它情况下，mp[row][col] = dt[row][col] + max(mp[row-1][col-1], mp[row-1][col]

发现和编辑距离的解法以及编程方法及其类似，所以不多做解释了，直接上代码

代码

如果使用矩阵存放数字三角形就会浪费很多空间， 比如数字三角形共 n 行，那么所需的空间就是 n*n, 如果使用一维数组来存放，那么所需的空间就是 (1+n)*n/2
它们的对应关系如下：

• 当 row = 0 时，dt[row][col] = dt[row]
• 当 row != 0 时，dt[row][col] = dt[(1+row)*row/2 + col]

计算 mp 矩阵的时候和编辑距离计算矩阵 d 的时候及其类似，
当计算这行的 mp 的时候，只需要上一行的 mp, 所以也可优化为一维数组

int get_dt(int *dt, int row, int col)
{
    return dt[(1+row)*row/2 + col];
}

int digital_triangle(int *dt, int line)
{
    int row, col, old, temp;
    int mp[line];

    mp[0] = dt[0];
    for (row = 1; row < line; row++) {
        mp[row] = get_dt(dt, row, row) + mp[row-1];
        old = mp[0];
        mp[0] = get_dt(dt, row, 0) + mp[0];
        for (col = 1; col < row; col++) {
            temp = mp[col];
            mp[col] = get_dt(dt, row, col) + max(old, mp[col]);
            old = temp;
        }
    }

    return max_of_array(mp, line);
}

以上代码需要注意的地方是如下两条语句：

1. mp[row] = get_dt(dt, row, row) + mp[row-1];
2. mp[0] = get_dt(dt, row, 0) + mp[0];

顺序不能颠倒，因为计算第一条语句的时候，在 row = 1 时需要用到 mp[0]. 如果把第二条语句放在上面，那么这时候 mp[0] 被覆盖为新值， 而第一条语句所需要的值为旧的 mp[0], 所以结果就不正确了