dynamic programming

 分治法和贪心法，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。

贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。

但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。

解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，找出其中最优(最大或最小)值的解。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题),对重复出现的子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。该方法也允许其通过自身子问题的解作出选择。

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。

20世纪50年代初美国数学家r.e.bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著dynamic programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

一道取自网上的例题:

从键盘上输入两个自然数n和k（n<=100,k<=10），从1，2，。。。，n中任取k个数，要求所取的k个数中，任意两个数不能相差1。编程求有多少种取法。

input

6 3

output

4

/*(1,3,5),(1,3,6),(1,4,6),(2,4,6)*/

[code]

<code>#include&lt;stdio.h&gt; int main() {     int n,k,i,j,a[100][100];     while(scanf("%d %d",&amp;n,&amp;k)!=eof)     {         for(i=1;i&lt;=n;i++)              a[i][1]=i;         for(i=2;i&lt;=k;i++)              a[1][i]=0;         for(i=2;i&lt;=n;i++)         {             for(j=2;j&lt;=k;j++)             {                 if(i&lt;=j)                      a[i][j]=0;                 else                       a[i][j]=a[i-2][j-1]+a[i-1][j];             }         }         printf("%d",a[n][k]);     }     return 0; }</code>

<code>[/code]</code>

<code>//分析</code>

<code>用 f(i,j)表示从1到i中任取j个数，任意两个数不能相邻：如果取i，则不能取i-1，必须从1到i-2中取j-1个数，即f(i-2,j-1).如果不取i，则只能从1到i-1中取j个数，即f(i-1,j).故f(i,j)= f(i-2,j-1)+ f(i-1,j); f[i,1]=i; f[1,i]=0;   这个递推式的结果是:矩形的上三角全0(a[1][1]元素除外),第一列为[1~n],其它元素为a[i-2][j-1]+a[i-1][j],最终所要的结果在a[n][k].(为什么是这样,自己多推几步就知道了)</code>