采纳动静布局思维求解数塔问题，c++实现
数塔问题
问题形容： 加粗款式从塔顶往下走，如何走过的步数最大
问题剖析：
- 数塔游戏（5层）
- 从塔顶到塔底，走过的值最大
- 从第一层开始，往左走还是往右走，变动两个4层他的问题，因而改问题存在子问题重叠性质
- 因为该问题要求走过的值最大，因而，该问题存在要求最优解，因而合乎动静布局用法
递归求解过程：
- 塔数据用二维数组存储d5,布局表格用maxD5存储(用来存储子问题的解),该构造是下三角构造
划分子问题：第1层走左还是走右取决去第2层哪个值最大，max(2)，第二层变动两个4层他的问题
- 递推公式：第一层的最优解有d0 + max{maxD1, maxD1}，第i层的最优解为di = amx{maxDi+1, maxDi+1}， 最初一层的最优解是本人，级maxDn-1 = dn-1
- 填表,表的最顶部的就是最优解
算法实现
#include<iostream>using namespace std; int max(int a, int b) { return a > b ? a : b;}int main() { int n = 5; int d[5][5] = {{8, 0}, {12, 15, 0}, {3, 9, 6, 0}, {8, 10, 5, 12, 0}, {16, 4, 18, 10, 9}}; int maxD[5][5] = {{0}, {0}, {0}, {0}, {16, 4, 18, 10, 9}}; // 先填写最初一层 for (int i = n-2; i>=0; i--) { for (int j = 0; j <= i; j++) { maxD[i][j] = d[i][j] + max(maxD[i+1][j], maxD[i+1][j+1]); } } // 输入初始值 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout<<d[i][j]<<"\t"; } cout<<endl; } cout<<"初始"<<endl; // 输入后果 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout<<maxD[i][j]<<"\t"; } cout<<endl; } return 0; }