经典动态规划问题——数字三角形

fatsky

发现鱼C没怎么有人将动态规划，补一发动态规划的帖子        //类似C++的伪代码

        先贴一下百科：
       
    动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家balabala...！@#￥%提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。
   
    看不懂没关系，把要点理一下：
   
    1、存在交叠子问题
    2、问题可以表现为多段决策（好像还是很难懂）
   
    动态规划的思想即通过 记忆化搜索 以空间换时间，以避免对同一问题的重复求解。讲通俗点，记忆化搜索就是把算过的数存起来，再用到的时候直接拿来用。
   
    求解动态规划问题，很重要的一点就是求出状态转移方程（如果弄到这儿题解基本就出来了），而状态转移方程实际上是一个递推关系，所以啰嗦了这么多，举个简单的栗子：数字三角形。
    问题如下：
   

             7
            
          3   8
         
        8   1   0
        
      2   7   4   4
      
    4   5   2   6   5

        上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

        注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

        输入数据

        输入的第一行是一个整数 N (1 < N <= 100)，给出三角形的行数。下面的 N行给出数字
        三角形。数字三角形上的数的范围都在 0和 100之间。

        输出要求

        输出最大的和。


        看到这个题目很容易想到DFS，然而当N == 100时会boom（自己试）。那么我们用动态规划的思想试试。
       
    首先，我们先给这个三角形标一下坐标：
    Ⅰ                 1
    Ⅱ              1   2
    Ⅲ            1   2   3
    Ⅳ          1   2   3   4
    Ⅴ        1   2   3   4   5
    我们约定第m行第n个数的坐标为（m,n)，F[m][n]为从(m,n)处加到最下面的最大值。
    使劲观察发现，这玩意儿可以划分为交叠子问题&#128540;，咋着个划分法，我们来分析一下：
   
    F[Ⅰ][1] = max(F[Ⅱ][1] , F[Ⅱ][2])  +  (Ⅰ,1)的值
    同理，
    F[Ⅱ][1] = max(F[Ⅲ][1] , F[Ⅲ][2])  +  (Ⅱ,1)的值
    F[Ⅱ][2] = max(F[Ⅲ][2] , F[Ⅲ][3])  +  (Ⅱ,2)的值
    以此类推，一直推到最底层，
    F[Ⅴ][1] 就是 (Ⅴ,1)的值（下面没有啦）。
    F[Ⅴ][2] 就是 (Ⅴ,2)的值。
    ……
    然后我们就求出了F[Ⅳ][ ]
    再求出F[Ⅲ][ ]
    F[Ⅱ][  ]
    最后是F[Ⅰ][1]（就像递归一样）
   
    所以，我们得出状态转移方程：
    F[m][n] = max(F[m - 1][n], F[m - 1][n + 1]) + (m,n)的值
    从下往上执行，就能得到答案。在这里F[][]是个数组，(m,n)处的值算完后就存到F[m][n]中，这就是记忆化搜索。
   
    代码网上有很多，此处不附。求解这类问题重要的是要把交叠子问题“抠”出来，想办法把它变成一个规律--状态转移方程，把它运用到代码里。