文档介绍：动态规划
终于来到了算法设计思想中最难,也最有趣的这部分,在去年的google笔试中,7道算法设计题有2道动态规划(Dynamic Programming)。
看了这么久的算法,这部分也是唯一感觉到了比较难的地方,
从这篇文章开始,将花连续的篇幅来讨论一些动态规划的问题。这包括书上介绍过的计算二项式系数,Warshall算法求传递闭包,Floyd算法求完全最短路径,构造最
有二叉查找树,背包问题和记忆功能。也包括一些其他问题的解题报告(动态规划确实很难,对这一章的内容,我将搜索一些其他类型的问题来写解题报告,以真正的
理解动态规划),例如矩阵连乘,最长公共子列,等等。
--------------------------------------------------------------------------------------------------------------------------------------------------
1,什么是动态规划(DP)?
非常重要!,不要认为概念不重要,理解的深刻,你才知道对于什么样的问题去考虑有没有动态规划的方法,以及如何去使用动态规划。
1)动态规划是运筹学中用于求解决策过程中的最优化数学方法。当然,我们在这里关注的是作为一种算法设计技术,作为一种使用多阶段决策过程最优的通用方法。
它是应用数学中用于解决某类最优化问题的重要工具。
2)如果问题是由交叠的子问题所构成,我们就可以用动态规划技术来解决它,一般来说,这样的子问题出现在对给定问题求解的递推关系中,这个递推关系包含了相
同问题的更小子问题的解。动态规划法建议,与其对交叠子问题一次又一次的求解,不如把每个较小子问题只求解一次并把结果记录在表中(动态规划也是空间换时间
的),这样就可以从表中得到原始问题的解。
关键词:
它往往是解决最优化问题滴
问题可以表现为多阶段决策(去网上查查什么是多阶段决策!)
交叠子问题:什么是交叠子问题,最有子结构性质。
动态规划的思想是什么:记忆,空间换时间,不重复求解,由交叠子问题从较小问题解逐步决策,构造较大问题的解。
---------
----------------------------------------------------------------------------------------------------------------------------------------
关于斐波拉切数列可以作为最简单的一个例子来解释动态规划的思想,在前面讲斐波拉切数列时说过了,不再叙述。
一般来说,一个经典的动态规划算法时自底向上的(从较小问题的解,由交叠性质,逐步决策处较大问题的解),它需要解出给定问题的所有较小子问题。动态规划的
一个变种是试图避免对不必要的子问题求解。如果采用自顶向下的递归来解,那么就避免了不必要子问题的求解(相对于动态规划表现出优势),然而递归又会导致对
同一个子问题多次求解(相对于动态规划表现出劣势),所以将递归和动态规划结合起来,就可以设计一种基于记忆功能的从顶向下的动态规划算法,在后面会讲。
------------------------------------------------------------------------------------------------------------------------------------------------
计算二项式系数:
在排列组合里面,我们有下面的式子(很容易用组合的定义来证明):
这个式子将C(n , k)的计算问题
表述为了(问题描述)C(n-1 , k -1)和C(n -1, k)两个较小的交叠子问题。
初始条件:C(n , n) = C(n , 0) = 1
我们可以用下列填矩阵的方式求出C(n , k):
该算法的时间复杂度是多少呢?可以大概的估计下,只填了下三角矩阵,为n*k/2  =  n*k,具体的次数为:
矩阵怎么填(填矩阵的顺序)?
按行来填矩阵:算法伪代码:
第1个for是控制行的,要填到第n行。第2个for来控制每行填到哪的,到i和k的较小值。从这2个for也可以看出复杂度是n*k。
实现:
package Section8;
/*第八章动态规划计算二项式系数*/
public class BinoCoeff {
/**
* ***@param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int resul