1，什么是动态规划（DP）？
非常重要！，不要认为概念不重要，理解的深刻，你才知道对于什么样的问题去考虑有没有动态规划的方法，以及如何去使用动态规划。
1）动态规划是运筹学中用于求解决策过程中的最优化数学方法。 当然，我们在这里关注的是作为一种算法设计技术，作为一种使用多阶段决策过程最优的通用方法。
它是应用数学中用于解决某类最优化问题的重要工具。
2）如果问题是由交叠的子问题所构成，我们就可以用动态规划技术来解决它，一般来说，这样的子问题出现在对给定问题求解的递推关系中，这个递推关系包含了相
同问题的更小子问题的解。动态规划法建议，与其对交叠子问题一次又一次的求解，不如把每个较小子问题只求解一次并把结果记录在表中（动态规划也是空间换时间
的），这样就可以从表中得到原始问题的解。
关键词：
它往往是解决最优化问题滴
问题可以表现为多阶段决策（去网上查查什么是多阶段决策！）
交叠子问题：什么是交叠子问题，最有子结构性质。
动态规划的思想是什么：记忆，空间换时间，不重复求解，由交叠子问题从较小问题解逐步决策，构造较大问题的解。
一个最简单的DP问题就是斐波拉切数列。f(n) = f(n-1) + f(n-2)
如果采用递归的方法计算，复杂度很高的。
还有一个问题就是矩阵的连乘问题， 计算最少的乘法次数，这些都是经典的DP问题。
Problem:有一个正整数序列,长度为N,每个元素最大值不超过MAX,求最长不上升子序列.
--------------------------------------------------------------------------------
经典的老得不能再老的问题,呵呵.这里主要是对流行的两种算法分析一下下.
两种算法,第一种为DP,大至的算法如下:
//a为存放序列的数组,aCount为序列的长度
int DP(int i,int height){
if(i >= aCount){
return 0
}
if(a[i] <= height){
return max(DP(i+1,height),DP(i+1,a[i])+1)
}else{
return DP(i+1,height)
}
}
这是一个一般的DP算法,需要两个参数, i为将要处理的值,height为当前最长不上升子序列中的最小值。当然，DP是要用表来进行优化的。很明显，时间复杂度为N^2，而空间复杂度为MAX*N（MAX为元素的最大值）.
--------------------------------------------------------------------------------
第二种是高效算法，大致如下：
//a为存放序列的数组,aCount为序列的长度
//b是一个全局数组，初始为0,bCount为b数组的计数器
int maxLen(){
b[1]=a[0]
bCount=2
for(i=1i<aCounti++){
//这一段可用2分法来优化，为了明晰算法,现在用的是线性查找
for(j=1j<bCountj++){
if(a[i]>b[j]){
break
}
}
//
if(a[i]>b[j]){
b[j]=a[i]
if(j+1 >bCount){
bCount = j+1
}
}
}
return bCount -1
}
大概思想是这样的，在b[i]中放的是长度为i的最长不上升子序列中的最后一个元素的最大值（请仔细体会）。我们在处理a[j]时，可以根据b[i]来进行查找，并更新。最后，b[]的有效数据的长度就是最长不上升子序列的长度。
可以用下面这个例子来说明：
开始时：
a[]={8,5,10,3,7,2}
b[]={0,8,0}
当处理a[1]=5时，发现长度为2的最长不上升子序列的最后一个为0，所以5>0，所以更新为:
b[]={0,8,5,0}
下一步，a[2]=10时，发现a[2]>b[1]，所以更新为:
B[]={0,10,5}
再下一步，a[3]=3时，更新为:
B[]={0,10,5,3}
再下一步，a[4]=7时，更新为:
B[]={0,10,7,3}
再下一步，a[5]=2时，更新为：
B[]={0,10,7,3,2}
所以，最后，最长长度为4,并且，最后一个元素的最大值为2
现在分析一下它的时间复杂度，如果在查找b[]的时候用二分的话，那么时间复杂度为nlog(n)，空间复杂度为N。
--------------------------------------------------------------------------------
现在比较一下两个算法。第一个算法有一个非常严重的问题，它的空间复杂度是依赖于MAX值的，如果MAX比较变态，那么内存会超出（不要和我说现在内存大。。），特别是给定的范围是Int的全范围时。第二个算法在空间方面的改进很明显。时间复杂度来说，第二个算法也有改进，当N>=10000时，估计DP会超时；而高效算法可以再撑几个数量级。当然，第二个算法实现起来稍微复杂了点，并且没有第一个算法那个明了。
