nyoj_176_整数划分（二）

nyoj_176_整数划分（二）_201404261715

整数划分（二）

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

把一个正整数m分成n个正整数的和，有多少种分法？

例：把5分成3个正正数的和，有两种分法：

1 1 3

1 2 2

输入

第一行是一个整数T表示共有T组测试数据(T<=50)
每组测试数据都是两个正整数m,n，其中(1<=n<=m<=100),分别表示要拆分的正数和拆分的正整数的个数。

输出

输出拆分的方法的数目。

样例输入

2
5 2
5 3

样例输出

2
2

来源

[张云聪]原创

上传者

张云聪

在整数划分（一）的基础上改编的，整数划分（一）里有详解：http://www.cnblogs.com/xl1027515989/p/3603533.html

针对此题，方法和整数划分（一）类似：

首先定义f ( i , j )为整数 i 分成 j 个整数的情况
经过分析可得f（i， j ）可转化为两个部分：
一：假设分成的 j 个整数中不包含1。。那么此时 f （ｉ－ｊ，ｊ）就是这部分的总情况，既然想让他不包含１，就先将ｊ个整数都分为１，此时ｉ变为ｉ－ｊ，再将ｉ分为ｊ个整数，这ｊ个整数再加上原先分的１，就肯定不会再有１出现了。如果i-j<j的话，f （ｉ－ｊ，ｊ）的值为0
二：　假设分成的ｊ个整数至少有一个１。。那么此时ｆ（ｉ－１，ｊ－１）

代码如下（一）：

 1 #include <stdio.h>
 2 int f(int m,int n)
 3 {
 4     if(m==n||n==1)
 5     return 1;
 6     else if(m<n)
 7     return 0;
 8     else if(m>n)
 9     return f(m-1,n-1)+f(m-n,n);
10 }
11 int main()
12 {
13     int T;
14     scanf("%d",&T);
15     while(T--)
16     {
17         int m,n;
18         scanf("%d%d",&m,&n);
19         printf("%d
",f(m,n));
20     }
21     return 0;
22 }
23 //AC
24 //首先 定义f ( i , j )为整数  i  分成 j  个整数 的情况
25 //经过分析可得f（i， j ）可转化为两个部分：
26 //一：  假设 分成的  j  个整数中 不包含1。。那么 此时 f （ｉ－ｊ，ｊ）就是这部分的总情况，既然想让他不包含１，就先将ｊ个整数都分为１，此时ｉ变为ｉ－ｊ，再将ｉ分为ｊ个整数，这ｊ个整数再加上原先分的１，就肯定不会再有１出现了。如果i-j<j的话，f （ｉ－ｊ，ｊ）的值为0
27 //二：　假设分成的ｊ个整数至少有一个１。。那么此时ｆ（ｉ－１，ｊ－１）
28 //
29

代码如下（二）：

 1 #include <stdio.h>
 2 int s[110][110];
 3 int f(int m,int n)
 4 {
 5     if(s[m][n]!=0)
 6     return s[m][n];//用数组保存已处理过的数据节约时间 
 7     if(m==n||n==1)
 8     return 1;
 9     else if(m<n)
10     return 0;
11     else if(m>n)
12     return s[m][n]=f(m-1,n-1)+f(m-n,n);
13 }
14 int main()
15 {
16     int T;
17     scanf("%d",&T);
18     while(T--)
19     {
20         int m,n;
21         scanf("%d%d",&m,&n);
22         printf("%d
",f(m,n));
23     }
24     return 0;
25 }
26 //AC