经典加速算法：动态规划

经典加速算法：动态规划

  
       最近刚刚老师讲的一个算法，拿出来和大家分享与讨论（算法的理解还是有难度的）：动态规划

      基本思想：其基本思想是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，适合于动态规划法求解的问题，经分解得到的子问题往往不是相互独立的，若用其他方法，往往有许多的问题被重复计算，耗费大量时间，如果能保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间，为了达到此目的，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
    步骤：
    （1）找出最优解的性质，并刻画其结构特征。
    （2）递归地定义最优解
    （3）以自底向上的方式计算出最优解
    （4）根据计算最优解时得到的信息，构造最优解
书中用动态规划解决的问题：
1.矩阵连乘问题
2.最长公共子序列
3.最大字段和
4.凸多变形最优三角剖分
5.多边形游戏
5.图像压缩
6.电路布线
7.流水作业调度
8.0-1背包问题
9.最优二叉搜索树
     我们讲的是多边形游戏，问题：
     多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边赋予一个运算符“+”或“*”。所有的边依次用整数从1到n编号。
    游戏第一步，将一条边删除。
    随后n-1步按以下方式操作：
    （1）选择一条边E及由E连接着的两个顶点V1与V2；
     （2）用一个新的顶点取代边E及由边E连接着的两个顶点V1与V2，将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
    最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
   问题：对于给定的多边形，计算最高分。
有兴趣朋友们可以去实现，源代码在这就不附了！