问题描述
　　求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。

分析
　　我们其实可以将这题转化一下.因为我们知道我们在划分时只要按不下降排列就不会有重复.并且每一份都不为0.我们可以形象的把n的k-自然数剖分看作把n块积木堆成k列，且每列的积木个数依次递增，也就是这n块积木被从左到右积木被堆成了"楼梯状"。比如，下图是10的几种4-剖分。
　　

　　现在，我们不妨把这三个图顺时针旋转90度，成为 ：

　　
　　对于这道题我们很容易可以想到一种状态表示方法,即用F(I,J,K)来表示把J无序划分成I份其中最大为K的划分方案数.那么,它就等于把J-K无序划分成I-1份,其中最大不超过K的划分方案数，状态转移方程就是
　　　　　　　　　
　　对应的pascal程序如下:
　　procedure dp;
　　var i,j,k,l:integer;
　　begin
　　　　assign(output,outputfile);
　　　　rewrite(output);
　　　　f[0,0,0]:=1;
　　　　for i:=1 to m do
　　　　　for j:=i to n do
　　　　　　for k:=1 to j do
　　　　　　　for l:=0 to k do
　　　　　　　　inc(f[i,j,k],f[i-1,j-k,l]);
　　　　for i:=1 to n do inc(count,f[m,n,i]);
　　　　writeln(count);
　　　　close(output);
　　end;

　　但是如果我们再把上图逆时针翻转90度，那么其实也就等于先在最下一行各摆上一块积木接下来也就是把I-J块积木放上去,并要保持楼梯状.我们可以发现其实上就是把I-J无序拆分成1～K份。那么我们可以得到如下动态转移方程
　 　　　　　　　　　　
　　procedure dp;
　　var i,j,k:integer;
　　begin
　　　f[0,0]:=1;
　　　for i:=1 to n do
　　　　for j:=1 to m do
　　　　　if j<=i then
　　　　　　for k:=0 to j do
　　　　　　　inc(f[i,j],f[i-j,k]);
　　　assign(output,outputfile);
　　　rewrite(output);
　　　writeln(f[n,m]);
　　　close(output);
　　end;

　　我们还可以把上述式子继续简化,因为我们发现,其实
　　　　　　　　　　F[I-1,J-1]=
　　那么我们在计算F[I,J]的时候就可以只做F[I,J]=F[I-1,J-1]+F[I-J,J]一次简单的加法运算就可以了,这样可以大大减少时间.
　　procedure dp;
　　var i,j,k:integer;
　　begin
　　　f[0,0]:=1;
　　　for i:=1 to n do
　　　　for j:=1 to m do
　　　　　if i>=j then f[i,j]:=f[i-j,j]+f[i-1,j-1];
　　　assign(output,outputfile);
　　　rewrite(output);
　　　writeln(f[n,m]);
　　　close(output);
　　end;
　　其实对于这题我们还可以继续优化,例如用滚动数组的方法使存处空间减少,这里就不再累赘了.
　　这里还想介绍一种更容易的做法.
　　若用F(I,J)表示把I无序划分成J份的方案数,则F(5,2)=({1,4},{2,3}); F(6,3)=({1,1,4},{1,2,3},{2,2,2})
　　你一定会发现如果把I无序划分为J份,那么它的前几个划分一定等于把I-1无序划分成J-1份每份前面加1的方案数.
　　那么后面那一部拆分方案又会等于什么呢?我们不妨将后面每一份中的每一个数减1,我们会发现它与F(I-J,J)是一一对应的.
证明如下
　　我们将一个自然数I划分为K份，为了避免重复，习惯于从小到大地划分。我们将数I分为K份的方法数记作F（I，K），可知：F（I，K）=F（I-K，K）+F（I-1，K-1）
证明：
　　设集合{A}为I的所有划分方案的第一项，0〈A〈=（I DIV K），设每一种划分方案的以后K-1个数为A+D1，A+D2，A+D3 …A+Dk-1，Di≤Di+1，于是：
　　　　　　　　　　　　
　　D的不下降排列数即I的首项是A的不同划分数 。
　　同理，设{B}为I-K的划分方案的首项集合，以后的K-1个数是B+C1，B+C2… B+Ck-1，所以，
　　　　　　　　　　　　
　　C的不下降排列数就是I-K的首项是B的不同划分数 ，
　　又因为：
　　　　　　　　　　　
　　可知当A-1=B 时 ，方案数相同，其中A能从2取到（I div k） ，而B∈[1，(I-k) div k]
即B∈[1,(I div k)-1], 所以，当A∈[2，I div k]时，方案总数是F（I-K，K）。又因为当A=1时，方案数是F（I-1，K-1），所以：
　　F（I，K）=F（I-K，K）+F（I-1，K-1）成立。

　　由此我们也可以推出与上面第三个程序一样的状态转移方程.