数塔问题（DP）

由上图可以看出，贪心算法似乎解决不了这个问题。我们如果使用动态规划

我们可以定义三个数组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会解决一些贪心所解决不了的问题