关于后端:采用动态规划思维求解数塔问题c实现

采纳动静布局思维求解数塔问题，c++ 实现

数塔问题

问题形容： 加粗款式从塔顶往下走，如何走过的步数最大

问题剖析：

1. 数塔游戏（5 层）
2. 从塔顶到塔底，走过的值最大
3. 从第一层开始，往左走还是往右走，变动两个 4 层他的问题，因而改问题存在子问题重叠性质
4. 因为该问题要求走过的值最大，因而，该问题存在要求最优解，因而合乎动静布局用法

5. 递归求解过程：

   1. 塔数据用二维数组存储 d5, 布局表格用 maxD5 存储 (用来存储子问题的解), 该构造是下三角构造

   2. 划分子问题：第 1 层走左还是走右取决去第 2 层哪个值最大，max(2)，第二层变动两个 4 层他的问题

      3. 递推公式：第一层的最优解有 d0 + max{maxD1, maxD1}，第 i 层的最优解为 di = amx{maxDi+1, maxDi+1}，最初一层的最优解是本人，级 maxDn-1 = dn-1
      4. 填表, 表的最顶部的就是最优解

算法实现

#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;    
}

后果