由上图可以看出，贪心算法似乎解决不了这个问题。我们如果使用动态规划
我们可以定义三个数组data，distance，direction
分别存放数据以及每一层要走的权重，还有就是方向。
这个题最大的权重和是59.
我们首先可以从下往上找，会容易一些，因为矩阵呈三角形状态，我们们的元素要走的方向即为右下和正下，我们通过比较该元素正下和右下的大小来选取每一层需要走的元素，最底层不用管，从倒数第二层开始推。
代码如下：
#include<iostream>#include<algorithm>using namespace std;int data[50][50]; //数塔元素数组 int distance1[50][50]; //记录每一次每一层的大小数组int direction[50][50]; //记录每次移动的方向0代表向下走，1表示向右下方走 int main(){int i,j,n;cout<<"请输入数塔元素的行数："<<endl;cin>>n;for(i = 1;i<=n;i++){for(j = 1;j<=i;j++){cin>>data[i][j]; //输入数塔元素的值distance1[i][j] = data[i][j];direction[i][j] = 0; //初始化方向向下走 }}for(i = n-1;i>=1;i--){for(j = 1;j<=i;j++){if(distance1[i+1][j] > distance1[i+1][j+1]){distance1[i][j] = distance1[i][j] + distance1[i+1][j];direction[i][j] = 0;}else{distance1[i][j] = distance1[i][j] + distance1[i+1][j+1];direction[i][j] = 1;}}} cout<<"max distance:"<<distance1[1][1]<<endl;j = 1;cout<<"路线：";for(i = 1;i<=n-1;i++){cout<<data[i][j]<<"->";j = j + direction[i][j];}cout<<data[n][j]<<endl;return 0;}结果：
有时候DP会解决一些贪心所解决不了的问题