(algorithm)动态规划

[Zhengy1995]

问题

在下面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大，路径上的每一步都只能往左下或者右下走，只需求出最大和即可，不必给出路径
（注：三角形的行数大于1小于100，数字为0 - 99）
    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

思路

首先是拆分问题，根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现。
关键步骤，动态规划有一类问题是从后往前推，有时候我们很容易知道：如果只有一种情况时，最佳的选择应该怎么做，然后根据这个最佳选择往前一步推导，得到前一步的最佳选择。
然后就是定义问题状态和状态之间的关系，我的理解是前面拆分的步骤之间的关系，用一种量化的形式表现出来，类似于高中学的推导公式，因为这种式子很容易用程序写出来，也可以说对程序比较亲和(也就是最后所说的状态转移方程式)。
找到最优解后，我们应该讲最优解保存下来，为了往前推导时能够使用前一步的最优解，在这个过程中难免有一些相比于最优解差的解，此时我们应该放弃，只保存最优解，这样我们每一次都把最优解保存了下来，大大降低了时间复杂度。