前言
动态规划就是dynamic planning，简称DP，是计算机算法中运动最多的算法之一。在POJ上做题目的时候， 会发现很多题目都是动态规划的思想，有必要去总结一下DP！
动态规划问题一般应用于具有最优子结构的问题，局部最优解常常能决定全局最优解，这样就可以一步步 从最简单的最优解得到整个复杂问题的最优解。能够用DP来解决的问题一般都具有下面两个性质：
最优子结构
就是一个问题通常可以划分为一个或者多个子问题，而且由子问题的最优解能够得到全局最优解，这样 整个问题就可以求解子问题最优解的形式。
重叠子问题
在用动态规划自顶向下(递归)来解决问题的时候，得到的子问题往往是重复遇见的，如果每次遇见都 不计代价地计算一次是不划算的，可以通过备忘录的方式(备忘录算法)将这些子问题的解记录下载，下次 遇见的时候只需去查表而不用重新计算。
一般的问题如果能提炼出以上两种性质，就可以很轻松地利用动态规划来解决。多说无益，来实战：
经典DP
LCS(最长公共子序列)问题是动态规划最经典的例子了。POJ1458问题具体描述：
s1：<x1,x2,x3....xm>
s2：<y1,y2,y3....yn>
求他们的公共序列的最大长度。这个问题显然存在最优子结构的问题：
情况一：若xm=yn，用反证法可以很容易地证明xm是公共子序列的最后一个字符，则子序列<x1,x2...xm-1>和<y1,y2...yn-1>的最长公共子序列的长度+1就是sm和sn的最长子序列的长度。
情况二：若xm!=yn,问题就可以转化为求sm-1和sn的最长公共子序列与sm和sn-1的最长公共子序列的较大者，这样问题就分解成为了两个较小的子问题。
分析到这里，就可以写出来递推关系了。对于求Xi:<x1,x2....xi>,Yj:<y1,y2...yj>的最长公共子序列 可以建立递推关系,其中c[i,j]代表最长公共子序列的长度：
= 0 if i=0||j=0
c[i,j] = c[i-1,j-1] if i,j>0 Xi=Yj
= max{c[i-1,j],c[i][j-1]} if i,j>0 Xi!=Yj
然后将上述公式转化为代码即可，使用多重循环和递归均可顺利得到答案，关于回文字符串的题目也可以 很容易用动态规划来解。
背包问题
网上有个《背包九讲》，把背包问题说的很全面，POJ1014也是经典的背包问题。背包问题的原型为：
有N件物品和一个容量为V的背包，物品的重量为c[i],价值为w[i],求背包中能装入的最大价值。
它也是一个动态规划问题，它满足最优子结构的性质：假设第i件物品在背包最优解的集合中，那么我们 拿出第i件物品，则剩下的物品是N件物品-i种物品和容量为V-c[i]的最优解。
根据限制条件的不同可以分为下面三个类型：
01背包
何为01背包，则每件物品只能放一次，即要么放(1)要么不放(0)。总结的方法为：
ZeroOnePack(cost,weight) for v=V..cost f[v]=max{f[v],f[v-cost]+weight}
注意v是一个倒循环，其中缘由就是大的背包是由容量小的背包决定的，如果按递增的顺序更新背包表， 那么容量大的背包的价值会越滚越大，而物品在一次循环中只有一件，所以是倒循环。
完全背包
何为完全背包，则每件物品可以放任意多次，这么时候方法会有变化：
CompletePack(cost,weight) for v=cost..V f[v]=max{f[v],f[v-cost]+weight}
注意这么时候for循环又变成了一个正循环，为什么放无限多次只需要改个循环倒顺就可以了呢？可这么 理解01背包中的逆序循环就是为了保证物品只放一次，而完全背包顺序就是可以无限放物品的结果，其中 深意需仔细体会。
多重背包
何为多重背包，则每件物品只能放有限次。总结的方法为：
MultiplePack(cost,weight,amount) if cost*amount>=V CompletePack(cost,weight) else int k=1 while k<amount ZeroOnePack(cost,weight) amount-=k k*=2; ZeroOnePack(amount*cost,amount*weight)
这里的多重背包就更看不明白了，我们暂且去读一读，第一个if当总重量超过V时就是一个完全背包的问 题，如果小于V则进行01背包的amount次循环，不过并非真正循环了amount次而是进行了一个二进制的 剪枝。
有了这三个解决方案，POJ1014就可以使用多重背包来解决。不过也不是说它只能用背包来解决，用DFS( 深搜)也能A这道题。事实上，想到用背包问题来解决问题和抽象出背包的模型比将代码写出来要难得多。
贪心
贪心算法也是一种动态对话算法，它的中心思想是为了得到全局最优解，每次都做出当前看起来最好的 选择，也就是说不从全局来考虑，子考虑当下的局部最优解。
贪心算法没有固定的框架，使用贪心算法能将问题简化不少，但是在使用之前必须得确保取当前的最优解 不会影响到全局最优解。
贪心算法最经典的例子就是田忌赛马POJ2287。