【算法】动态规划：数塔问题

#include <iostream>
#include <algorithm>
using namespace std;
/*
数塔问题：
描述：从数塔的顶层出发，在每一个节点可以选择左右方向，一直走到最底层。
求找出一条路径，使得路径上的数值和最大。 

d[n][n] 数塔，三角矩阵 
maxAdd[n][n] 存储动态规划每一步决策结果
path[n][n] 存储每一次觉得所选择的数组在d[n][n]中的列下标

maxAdd[n-1][j] = d[n-1][j], 0 <= j <= n-1 
maxAdd[i][j] = d[i][j] + max{maxAdd[i+1][j], maxAdd[i+1][j+1]}, 0 <= i <= n-2, 0 <= j <= i;

0 <= i <= n-2, 0 <= j <= i
path[i][j] = j, maxAdd[i+1][j] > maxAdd[i+1][j+1] 
path[i][j] = j + 1,  maxAdd[i+1][j] <= maxAdd[i+1][j+1] 

*/
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int DataTower(int n, int d[5][5]){
	int maxAdd[n][n] = {0};
	int path[n][n] = {0};
	int i, j;
	
	//初始化底层决策结果 
	for (j = 0; j < n; j++){  
		maxAdd[n-1][j] = d[n-1][j];
	}
	
	//进行第i层决策
	for (i = n - 2; i >= 0; i--) {
		for (j = 0; j <= i; j++){
			if (maxAdd[i+1][j] > maxAdd[i+1][j+1]){
				maxAdd[i][j] = d[i][j] + maxAdd[i+1][j];
				path[i][j] = j;
			}
			else{
				maxAdd[i][j] = d[i][j] + maxAdd[i+1][j+1];
				path[i][j] = j + 1;
			}
		}
	}
	cout << "路径为：" << d[0][0];
	j = path[0][0]	;
	for (i = 1; i < n; i++){
		cout << "-->" << d[i][j];
		j = path[i][j];
	}
	cout << endl;
	return maxAdd[0][0];
}
int main(int argc, char** argv) {
	int d[5][5] = {8, 0, 0, 0, 0,
					12, 15, 0, 0, 0,
					3, 9, 6, 0, 0,
					8, 10, 5, 12, 0,
					16, 4, 18, 10, 9};
					
	cout << "数塔的最大数值和：" << DataTower(5, d);
	return 0;
}