SCAU OJ题 9714 圣诞礼物

SCAU OJ题 9714 圣诞礼物

9714 圣诞礼物

时间限制:1000MS 内存限制:1000K

题型: 编程题 语言: 无限制

Description

圣诞节到了，圣诞老人给 N 个小朋友准备了 M 个同样的礼物。每个小朋友有一个袜子（袜子不编号，无区别，认为袜子都相同），

圣诞老人将 M 个礼物装到 N 个袜子中的放法有多少种？

注意：

1）若M=7 N=3，那么5,1,1的放法和1,5,1的放法算是同一种装法。

2）允许袜子为空。

3）M和N无大小关系，M可以比N大，M也可以比N小。

Input

输入数据包含两个整数 M,N。1<=M,N<=50。

M在前，N在后，中间空格。

Output

输出共有几种不同的放法。

Sample Input

7 3

Sample Output

8

思路：这个问题其实可以转化为整数n的m划分，也就是“正整数 n 的所有划分中，最大加数小于等于 m 的划分”，M个礼物分给N个小朋友，M就是n，N就是m，刚好反过来了。

#include <iostream>using namespace std;int q(int n, int m)
{if(n<1||m<1)//不符合实际情况return 0;if(n==1||m==1)return 1;if(n<m)//m不能大于nreturn q(n,n);if(n==m)//动规思想，正整数n的划分由n1=n的划分和n1<=n-1的划分组成return q(n,m-1)+1;return q(n,m-1)+q(n-m,m);//动规思想，正整数n最大加数n1不大于m的划分由n1=m的划分和n1<=m-1的划分组成
}int main()
{int n,m;cin>>n>>m;cout<<q(n,m);
}