(3).动态规划(Dynamic Programming,以下简称DP)
俗话说，要看一个人的算法水平，只要看一下他做DP题的水平就OK了，而在ACM这个多变的赛场上，几多算法沉浮，唯有DP几乎从未消失过，如果你问我什么类型的题在赛场上出现的概率最高，我可以毫不犹豫地告诉你，是DP。由此也可以看出，DP的地位有多么重要，那么这样一个几乎每场比赛都会出现的题型，应该很难啊，为什么要让我们从DP入手呢？确实，DP是很难，其变型之多，覆盖知识面之广，确实让人望而生却，但是，我想说下如何入门DP题。首先是DP几个最为基本的模型，LCS(最长公共子序列)，LIS(最长上升子序列)，最大公共子段和，数塔问题，矩阵连乘等几个最为经典的问题，大家一开始的时候可能难以理解DP中自底向上，重叠子结构等基本思想，对于这几道问题可以先看一下别人的代码和书上的讲解，然后再自己反复地理解，理解了之后再自己敲一下代码，如果有地方实在不理解，可以先放一下，去看看其他题，回过头来再想一下以前的题，也许会有豁然开朗的效果。吃透了DP的几个经典问题之后，就可以做一下这些经典问题的变型了，比如最大公共子段和的变型——最大子矩阵和最大m子段和，最长公共子序列和最长上升子序列的变型——最长公共上升子序列等等。并且可以尝试接触DP的一些重要的应用，最重要的要数背包问题，背包问题是DP一个很大的分支(算是分支吧，我找不到其他更好的词来形容他了)，同样也有非常多的变型，如最为基础的01背包，以及扩充出去的多重背包，完全背包，分组背包，树型DP(这个知识点我待会会介绍)中应用非常多的泛化背包等等，下面我把最为基本01背包，多重背包和完全背包讲一下，首先是最简单的01背包，伪代码如下：
for i=1..N
for v=V..0
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
这里为什么要倒推呢？其实道理很简单，因为这里其实是利用类似滚动数组的概念，只不过他连2个数组都不用开了，只需要开一个数组就可以了，这是为什么呢？因为传统的二维数组中f[i][v]的值是由max( f[i-1][v], f[i-1][ v-c[i] ] + w[i] )得来的，所以每次f[v]的值是由上层循环中fv’得来的，所以改成了一维数组后，如果从小到大循环的话，在计算完成f[v] 之后，就会在计算f[v’](v’ >=v)时发生错误，因为原本计算f[v’]所需的上层循环中的f[v]的值已经被新的值覆盖掉了，故必须从大到小循环。其次是多重背包，完全可以化为01背包问题，不过是把相同价值的同种类物品看成多个价值相同的不同种类物品，即比01背包多了一重循环，要注意的是这两层循环都要从大到小，原理和01背包类似。最后是完全背包问题，伪代码如下：
for i=1..N
for v=0..V
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑 “加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。这里我向大家推荐一下浙江大学的DD牛所写的《背包九讲》，是背包入门及提高的最为经典的资料。现在就要讲一下树型DP了，树型DP其实就是DP，只不过是建立在树模型之上的DP罢了，不过树型DP说起来虽然简单，确是DP中相当困难的一个知识点，要好好理解，多做些题才行。最后是状态压缩DP，这也是一个DP的一个难点，所谓的状态是指利用二进制或者其他进制的数来表示状态从而达到空间上压缩的目的，这一类的状态设计一般都很巧妙，而且涉及的众多位运算对于编码能力也是一个相当大的挑战，介于状态压缩DP是用记忆化搜索(所谓记忆化搜索，是DP的另外一种递归的实现形式，即所谓的自顶向下)来实现的，又要牵涉到搜索的知识点，建议等学习了相关的内容之后再回过来头来学习这个知识点。状态压缩的经典题有棋盘覆盖问题，炮兵阵地等。
本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-/a/tongxinshuyu/article-24376-2.html
