nyoj_176_队花的烦恼二

nyoj_176_队花的烦恼二_201404262008

队花的烦恼二

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

难度：4

描述

ACM队队花C小+最近在X大OJ上做题，竟发现了一道做不出来的…水题！她快郁闷死了……也许是最近状态不太好吧……她希望大家能帮帮忙：把一个整数分成若干个不为零的整数，问有多少种不同分法。

例：7 3 其中的分法：1 1 5，1 5 1，5 1 1是同一种分法。

输入

有多组测试数据
每组数据都有两个整数n,m（6<=n<=500,2<=m<=6）
n表示该整数，m表示把n分成m份

输出

对每一组测试数据，输出不同的分法数

样例输入

7 3
10 2
20 3

样例输出

4
5
33

来源

改编

上传者

Never

 1 #include <stdio.h>
 2 int s[550][550];
 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 m,n;
17     while(scanf("%d%d",&m,&n)!=EOF)
18     {        
19         printf("%d
",f(m,n));
20     }
21     return 0;
22 }

类似整数划分（二）：http://www.cnblogs.com/xl1027515989/p/3691975.html