C++ 数字三角形(动态规划)_c++数字三角形

一、题目

   有三种方法实现： 这里就求权值之和最大的，最小的类似就不分析了。

   1.自底向上  缺点：算法复杂，重复计算

   2.自顶向下  缺点：重复计算，浪费时间

   3.动态规划 思路和自底向上、自顶向下一样，只不过开多一个数组opt存储计算过的到达a[i][j]的权值之和最大的数

二、思路：

     方法1：自底向上

     1.从最后一行出发，例如，最后一行的2：

        如何得到走到2的权值之和最大数？（用递归）

               那就要先得到走到左上角的数（7）的权值之和最大的数，正上方的数（4）的权值之和最大的数。

        再比较两者哪个大，大的一个加上最后一行的数2，就是走到2的权值之和最大的数；

        同样，如何得到走到7的权值之和最大的数？或者是走到4的权值之和的最大数

              就要先得到7的左上角的数（8）的权值之和的最大数，和正上方的数（1）的权值之和的最大数，再

        比较这两个权值之和哪个大，大的加上7；

        ……

        一直递推到第一行的数a[0][0]，返回a[0][0]的值，然后回归，求得到达2的权值之和的最大数；

     2.比较走到最后一行（4，5，2&#x