相信学过编程的人都听说过动态规划。初学者都认为动态规划很难，其实动态规划并不难，只是有的时候很复杂而已。今天就跟大家浅谈动态规划吧。
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
动态规划算法与其它算法相比，大大减少了计算量，丰富了计算结果，它没有一个固定的解题模式，技巧性很强，是构造最优解的常用方法。
多数编程教科书动态规划一章里的第一个例子就是——
最长递增子序列：输入一个整数序列，求出其最长子序列的长度，使得子序列里前一项总比后一项小。（注：子序列的每一项都属于原数列，且不一定连续）
举个例子，假如输入的数列为3 6 1 4 2 8 9 5 7，那么它的最长子序列一共有五个（36 8 9；3 4 8 9；1 2 8 9；1 2 5 7；3 4 5 7），最长子序列的长度是4。
那么我们该怎么编程解决呢？暴力而容易想到的方法是把每一个整数作为最长递增子序列的最后一个整数然后进行深度优先搜索。然而如果你仔细思考，你会被这个方法的时间复杂度吓住。设原序列的长度为n，那么就有O(n)个整数需要被搜索，每层搜索又会递归到O(n)个下一层搜索，而搜索又有O(n)层，也就是说数据如果坑，时间复杂度可能达到O(n^n)。要是n值有20，计算机就已经算的够累了，更不说n=2000的情况了。这就到了动态规划大显神通的时候了。先说一句，使用动态规划要注意空间和时间之间的转化以及递推的关系。
我们先看递推的关系。每个新加的整数都会接上前面的一个序列或者自己组成一个新的序列。
然后就要扩大空间了。既然要求最长长度，那么就用一个数组记录以当前数为最后一位的最长子序列长度。
下面第一遍扫这n个数（扫到第i个数时需要把第1到i-1个数中小于第i个数的最大值找出，然后加1），
序列：3 6 1 4 2 8 9 5 7；
数组：1 2 1 2 2 3 4 3 4；
最后，将数组扫一遍，找出最大值。这个最大值就是最长子序列的长度。
C语言代码实现如下：
#include
#include
int main(){
int i,j,n,max=0;
int a[2001],b[2001];
//读入及初始化
scanf("%d",&n);
for(i=1;i
b[i]=1;
scanf("%d",&a[i]);}
//扫第一遍
for(i=1;i
for(j=1;j
if(a[i]>a[j]&& b[i]
b[i]=b[j]+1;
//扫第二遍
for(i=1;i
if(max
max=b[i];
printf("%d",max);
return 0;}
你可以看到代码量出奇的少。这是因为本题的递推关系简单，而且可以完全避免深度优先搜索。遇到难的动态规划的题，其实只要找出递推关系，用空间存储合适的变量也能引刃而解。既然说到递增序列了，下面给大家留一个思考题，有兴趣可以尝试一下：
输入一个长度为n的互异整数数列，定义交换两个整数在序列中的位置称为一次操作。输出最小操作次数，使得原序列变成递增数列。（提示：并查集）
最后，祝福大家
元宵节快乐！
