文档介绍：动态规划浅谈 
    动态规划( dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,技巧性也很强。利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果,与贪婪算法不同的是,在贪婪算法中,每采用一次贪婪准则,便做出一个不可撤回的决策;而在动态规划算法中,还要考察每个最优决策序列中是否包含一个最优决策子序列,即问题是否具有最优子结构性质。
    动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质:最优子结构性质和子问题重叠性质。
1 、最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
2 、子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简 单地查看一下结果,从而获得较高的解题效率。
当我们已经确定待解决的问题需要用动态规划算法求解时,通常可以按照以下步骤设计动态规划算法:
1 、分析问题的最优解,找出最优解的性质,并刻画其结构特征;
2 、递归地定义最优值;
3 、采用自底向上的方式计算问题的最优值;
4 、根据计算最优值时得到的信息,构造最优解。
1 ~ 3 步是动态规划算法解决问题的基本步骤,在只需要计算最优值的问题中,完成这三个基本步骤就可以了。如果问题需要构造最优解,还要执行第 4 步; 此时,在第 3 步通常需要记录更多的信息,以便在步骤 4 中,有足够的信息快速地构造出最优解。
 下面通过几个经典例子来演示一下动态规划的具体思想.
例1:数字三角形
如下所示的数字三角形:
                    1
2           3
                4   5   6
              7   8   9   10
    从顶向下找出一条权值最小的路径。(路径的权值等于路径上各结点的值的和)
用f(i , j)表示位置i , j上最优的权值。则很容易得出递归公式:
        x=f(i+1,j)+a[i,j]
        y=f(i+,j+1)+a[i,j]
        f(i,j)=x<y?x:y
其中a[i, j]为该位置上的结点值。
由此可以得到一个非常简单的搜索算法:
int search(int i, int j){
       int x, y;
       if(i==n)return array[i][j];
       x = search(i+1,j)+array[i][j];