如下图是一个数塔，从顶部出发在每一个节点可以选择向左或者向右走，一直走到底层，要求找出一条路径，使得路径上的数字之和最大。

9
12	15
10	6	8
2	18	9	5
19	7	10	4	16

算法分析

我们可以这样想，从最后一层倒过来看，到倒数第二层，可以选择一个较大的路径，例如，假设我们一步走到了2这里，下一步应该怎么走？只有19或7这两种选择，既然我们想让总的路径之和最大，那我们肯定每一步都要选大的。我们人脑编译器是很简单的，每次只需要倒着推，到最后一个数据就是我们的最大路径。

数据结构

假设这个数塔的层数是N，我们可以将这个数塔放在一个NxN的data数组里，也许只需要下三角矩阵i>=j。另外，我们还就可以将每一步最大的路径的数据保存在dp数组里。用两重循环来遍历数组，我们要倒着推，所有要i–，二维的j是从左往右，j++。

data
9
12	15
10	6	8
2	18	9	5
19	7	10	4	16

dp
59
50	49
38	34	29
21	28	19	21
19	7	10	4	16

代码

#include <iostream>
#define N 101 
//最后一层的我们需要多加一层空白数据，不然会数组下标错误
using namespace std;

int max(int a, int b){
    return a>b?a:b;
}

int data[N][N];//全局变量已初始化0
int dp[N][N];

int main() {
    int n;
    cout<<"请输入数塔的层数：（不超过100）"<<endl;
    cin>>n;
    cout<<"请输入塔的数据"<<endl;
    for (int i = 0; i < n ; ++i) {
        for (int j = 0; j <= i ; ++j) {
            cin>>a[i][j];
        }
    }
    for (int i = n-1; i >=0 ; --i) {
        for (int j = 0; j <= i ; ++j) {
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+data[i][j];
            //最后一层dp数据和data一样max(0,0)
        }
    }
    cout<<"最大的路径和是："<<dp[0][0];
    
    return 0;
}

输出

最大路径和是：59

优化

输出路径

题目可能会要求我们输出我们是怎么走的，在两个表都填写完整后，第一步不用说，肯定的是data[0][0]，之后，我们用dp[i][j]（还是从dp[0][0]开始）数据减去data数组的这一个位置的数据,我们可以倒着想，我们是用下面两个数据的较大的一个加上data[i][j]数据得到这个dp[i][j]。相减的结果就是较大的那个dp[i+1][j]或者是dp[i+1][j+1]。我们就可以确定是选择了这个路径data[i+1][j]或data[i+1][j+1]。因为这一次我们是正着走的，一条路走到底，每次都选dp大的那一个data数据，只需要循环N-1次就可以了(第一步已确定)。

void print()
{
    int node_value;
    // 首先输出塔顶元素
    cout << "最大路径：" << data[0][0];
    int j = 0;
    for (int i = 0; i < n-1; ++i)
    {
        node_value = dp[i][j] - data[i][j];
        if (node_value == dp[i][j + 1]){
            j++;//记录节点的列，输出要用
            cout << "->" << data[i+1][j];
        }//右边的大，应该往右走
        else{
            cout << "->" << data[i+1][j];
        }//左边的大，应该往左走 
    }
    cout << endl;
}

输出

最大路径：9->12->10->2->19

空间优化

其实dp数组里的数据不需要每一层都储存起来，用过之后就没用了，我们可以用覆盖的方法将二维数组优化为一维数组，也就是滚动数组。

参考博客：
动态规划：数塔问题——卡尔曼和玻尔兹曼谁曼