《数的划分方法总结》由会员分享，可在线阅读，更多相关《数的划分方法总结（5页珍藏版）》请在金锄头文库上搜索。
1、数的划分问题：将整数 n 分成 m 个正整数，不考虑顺序，例如：n=7, m=3，下面三种分法被认为是相同的。1， 1， 5; 1， 5， 1; 5， 1， 1;问有多少种不同的分法。Inputn， m (6n=10000， 2=m=1000)Output一个整数，即不同的分法。Sample Input73Sample Output4四种分法为： 1,1,5; 1,2,4; 1,3,3; 2,2,3;方法 1：dfs效率低下方法 2 ：模型转化。我们其实可以将这题转化一下 .因为我们知道我们在划分时只要 按不下降排列就不会有重复.并且每一份都不为 0.我们可以形象 的把n的m-自然数剖分看作把
2、n块积木堆成m列，且每列的积 木个数依次递增，也就是这 n 块积木被从左到右积木被堆成了 楼梯状。比如，下图是10的几种 4-剖分。对于这道题我们很容易可以想到一种状态表示方法 ,即用 F(I,J,K) 来表示把J无序划分成I份其中最大为K的划分方案数那么，它就 等于把J-K无序划分成I-1份，其中最大不超过K的划分方案数， 状态转移方程就是fwc=hk-h方法 3：但是如果我们再把上图逆时针翻转 90 度，那么其实也就等于先 在最下一行各摆上一块积木接下来也就是把 I-J 块积木放上去,并要保持楼梯状 . 我们可以发现其实上就是把I-J 无序拆分成K(1=k=i-j)份。那么我们可以得到如下
3、动态转移方程procedure dp;var i,j,k:integer;beginf0,0:=1;for i:=1 to n dofor j:=1 to m doif j=j thenfi,j:=fi-j,j+fi-1,j-1;writeln(fn,m);end.证明方法 1：N 数分 m 份，若最小值为 1 ，则 1 占一份，剩余 N-1 数分 m-1 份； 若最小值不为1,则i-j还可以分成j份。i-j就相当于把每份(即j份)都减去1比如 f73 中的 f43 为 1 1 2 对应 f73 中的 2 2 3 证明方法 2 ：若用F(I,J)表示把I无序划分成J份的方案数，则F(5,2)=
4、(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的所有划分方案的第一项，0A= (I DIV K),设每一种划分方案的以后K-1
5、个数为A+D1，A+D2，A+D3A+Dk-1,DiSDi+1，于是：D的不下降排列数即I的首项是A的不同划分数。同理，设B为I-K的划分方案的首项集合，以后的K-1个数是 B+C1，B+C2B+Ck-1，所以，C的不下降排列数就是I-K的首项是B的不同划分数， 又因为：Q二(必一1尸疋十工刀可知当A-1=B时，方案数相同，其中A能从2取到(I div k),而 BG1，(I-k) div k即BG1川div k)-1,所以，当AG2,Idiv k时，方案总数是F(l-K，K)。又因为当A=1时，方案数是F (I-1，K-1)，所以：F (I，K) =F (I-K，K) +F (I-1，K-1)成立。
