例谈四种常见的动态规划模型动态规划是解决多阶段决策最优化问题的一种思想方法，本文主要结合一些例题，把一些常见的动态规划模型，进行归纳总结。
（一）、背包模型可用动态规划解决的背包问题，主要有01背包和完全背包。
对于背包的类型，这边就做个简单的描述：n个物品要放到一个背包里，背包有个总容量m，每个物品都有一个体积w[i]和价值v[i]，问如何装这些物品,使得背包里放的物品价值最大。
这类型的题目，状态表示为：f[j]表示背包容量不超过j时能够装的最大价值，则状态转移方程为：f[j]:=max{f[j-w[i]]+v[i]},边界：f[0]:=0;简单的程序框架为：beginreadln(m,n);for i:=1to n do readln(w[i],v[i]);f[0]:=0;for i:=1to m dofor j:=1to n dobeginif i>=w[j]then t:=f[i-w[j]]+v[j];if t>f[i]then f[i]:=t;end;writeln(f[m]);end.这类型的题目应用挺广的（noip1996提高组第4题，noip2001普及组装箱问题，noip2005普及组采药等），下面一个例子，也是背包模型的简单转化。
货币系统(money)【问题描述】母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。
他们对货币的数值感到好奇。
传统地，一个货币系统是由1，5，10，20或25，50，100的单位面值组成的。
母牛想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。
使用一个货币系统{1,2,5,10,..}产生18单位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。
写一个程序来计算有多少种方法用给定的货币系统来构造一个确定的面值。
【输入格式】货币系统中货币的种类数目是v(1≤v≤25)；要构造的面值是n(1≤n≤10,000)；第1行:二个整数，v和n；第2..v+1行：可用的货币v个整数(每行一个)。
【输出格式】单独的一行包含那个可能的构造的方案数。
【输入样例】310125【输出样例】10[分析]：此题是个背包模型，只是问题的解是构造方案数,设w[j]为第j种币值，状态f[i]：构造面值为i时可能的方案数，则状态转移方程为：f[i]:=∑f[i-w[j]]，i>=w[j],边界：f[0]:=1;f[n]即为问题的解。
注意：由于此题的数据规模比较大，所以要用到高精度加法，估计最大的数据可以达到73位，为节约程序时间和空间效率，还采用了万进制的高精度加法。
参考程序如下：varf:array[0..10000,1..20]of integer;long:array[0..10000]of integer;//存储位数w:array[0..25]of integer;n,m,i,j,k:integer;procedure add(r,t:integer);//万进制高精度加var i,k:integer;beginif long[t]<long[r]then long[t]:=long[r];k:=0;for i:=1to long[t]dobeginf[t,i]:=(f[t,i]+f[r,i]+k);k:=f[t,i]div10000;//每一个存4位,万进制，这样省时省空间f[t,i]:=f[t,i]mod10000;end;while k>0do//进位处理begininc(long[t]);f[t,long[t]]:=k mod10000;k:=k div10000;end;end;procedure main;var i,j:integer;beginf[0,1]:=1;long[0]:=1;for i:=1to m dofor j:=w[i]to n do add(j-w[i],j);write(f[n,long[n]]);//输出答案,由于每个存4位,所以有时需要补零for i:=long[n]-1downto1dobeginif f[n,i]<10then write('000')else if f[n,i]<100then write('00')else if f[n,i]<1000then write('0');write(f[n,i]);end;end;beginassign(input,'money.in');reset(input);assign(output,'money.out');rewrite(output);readln(m,n);for i:=1to m do readln(w[i]);main;close(input);close(output);end.（二）、资源分配模型资源分配模型的动态规划，这类型的题目一般是：给定m 个资源，分配给n 个部门，第i 个部门获得j 个资源有个盈利值，问如何分配这m 个资源能使获得的盈利最大，求最大盈利。
这类型的题目一般用资源数做状态，数组f[i,j]表示前个i 个部门分配j 个资源的最大盈利，则状态转移方程为：f[i,j]:=max{f[i-1,k]+value[i,j-k]}(0<=k<=j)程序框架如下：var i,j,k:longint;beginfor i:=1to n dofor j:=0to m dofor k:=0to j doif f[i-1,k]+value[i,j-k]>f[i,j]then f[i,j]:=f[i-1,k]+value[i,j-k];writeln(f[n,m]);end;资源分配类型典型应用是花店橱窗(flower.pas)设置，没做过的同学可以自己去练习一下，下面的一个例题，也是此类型的转换。
[问题描述]农夫ion 放完马以后，需要把马儿关回马厩。
为了做好这件事，ion 让马排成一行跟着他入马厩。
他想出了一个就近入厩的办法：让前p 1匹马进入第一个马厩，然后的p 2匹马进入第二个马厩，如此类推。
而且，他不想让任何一个马厩（共k 个）留空，还有所有的马都进入马厩。
已知ion 只有黑色和白色两种颜色的马，然而并不是所有的马都能相处融洽。
假如有i 匹黑马和j 匹白马同在一个马厩，那么它们之间的不愉快系数为i*j。
马厩总的不愉快系数等于k 个马厩的不愉快系数之和。
请帮忙把n 匹马按顺序放入k 个马厩中（即求一种p 1,p 2…的安排方案），使得总的不愉快系数最小。
[输入格式]输入第一行为一个n 和k；（n<=100,k<=n）;输入第二行为n 个数0和1，0表示白马，1表示黑马[输出格式]一行，最小的不愉快系数。
样例输入32101样例输出1分析：设f[i,j]：表示将前i匹马放入前j个马厩，得到的最小不愉快系数。
w[i,j]：表示将第i至第j匹马放入同一个马厩所得到的不愉快系数。
状态转移方程为：f[i,j]=min(f[k,j-1]+w[k+1,i]){j-1<=k<i}注意边界条件：f[i,1]:=w[1,i];f[i,i]:=0;参考程序如下：const maxn=100;maxk=100;varf:array[1..maxn,1..maxk]of longint;w:array[1..maxn,1..maxn]of longint;a:array[1..maxn]of longint;i,j,k,k1,n,s1,s2:integer;beginassign(input,'horse.in');reset(input);assign(output,’horse.out’);rewrite(output);readln(n,k);for i:=1to n do read(a[i]);for i:=1to n do//求w[i,j]for j:=i to n dobegins1:=0;s2:=0;for k1:=i to j doif a[k1]=0then inc(s1)else inc(s2);w[i,j]:=s1*s2;end;for i:=1to n do//初始化for j:=1to k dof[i,j]:=maxint;for i:=1to n do//边界条件beginf[i,i]:=0;f[i,1]:=w[1,i];end;for j:=1to k do//动规过程for i:=j to n dofor k1:=j-1to i-1doif(k1>0)and(j-1>=1)and(f[k1,j-1]<>maxint)thenf[i,j]:=min(f[k1,j-1]+w[k1+1,i],f[i,j])writeln(f[n,k]);close(input);close(output);end.（三）、区间类模型区间类模型的动态规划，一般是要求整段区间的最优值，子问题一般是把区间分成两个子区间。
一般用二维数组表示状态，例如f[i,j]表示从i到j的最优值。
则状态转移方程就是跟子区间之间的关系，下面我们用个典型的例子讲解这个模型的应用。
[问题描述]给定一个具有n（n<50）个顶点（从1到n编号）的凸多边形，每个顶点的权均已知。
问如何把这个凸多边形划分成n-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行顶点数n第一行n个顶点（从1到n）的权值输出格式：最小的和的值,各三角形组成的方式输入示例：5122123245231输出示例：t he minimum is:12214884the formation of3triangle:345,153,123分析:这是一道很典型的区间模型动态规划问题。
设f[i,j]（i<j）表示从顶点i到顶点j 的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：f[i,j]=min{f[i,k]+f[k,j]+s[i]*s[j]*s[k]}(i<k<j)目标状态为：f[1,n]但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形甚至实形的范围，所以我们还需用高精度计算，但这是基本功，程序中就没有写了，请读者自行完成。
参考程序vars:array[1..50]of integer;f:array[1..50,1..50]of comp;d:array[1..50,1..50]of byte;n:integer;procedure init;var i:integer;beginreadln(n);for i:=1to n do read(s[i]);end;procedure dp;//动态规划var i,j,k:integer;beginfor i:=1to n dofor j:=i+1to n do f[i,j]:=maxlongint;//赋初始值for i:=n-2downto1dofor j:=i+2to n dofor k:=i+1to j-1doif(f[i,j]>f[i,k]+f[k,j]+s[i]*s[j]*s[k])thenbeginf[i,j]:=f[i,k]+f[k,j]+s[i]*s[j]*s[k];d[i,j]:=k;//记录父节点end;end;procedure print(i,j:integer);//输出每个三角形beginif j=i+1then exit;write(',',i,'',j,'',d[i,j]);out(i,d[i,j]);out(d[i,j],j);end;procedure out;//输出信息beginwriteln('the minimum is:',f[1,n]:0:0);writeln('the formation of',n-2,'triangle:');write(1,'',n,''d[1,n]);out(1,d[1,n]);out(d[1,n],n);end;begin//主程序init;dp;out;end.区间模型的动态规划，在历届的信息学竞赛，应用非常广泛，如noi95的石子合并问题，noip2003普及组的数字游戏，noip2006提高组第1题等。