整数划分

#include <iostream> using namespace std; int f(int n,int m) { if(n==0 || m==1) return 1; if(n<m) return f(n,n); else return f(n,m-1) + f(n-m,m); } int main() { ios::sync_with_stdio(0); int num; cin>>num; for(int i=1;i<=num;++i) { int n,m; cin>>n>>m; cout<<f(n,m)<<endl; } return 0; }

集合划分

#include <iostream> using namespace std; int f(int n, int m) { if(n==m || m==1) return 1; return f(n-1,m-1) + m*f(n-1,m); } int main() { int sum = 0; int n,m; cin>>n>>m; for(int i=1; i<=m; i++) sum += f(n,i); cout<<sum; return 0; }

区别：

举个通俗易懂的例子，

整数划分问题就等同于将n个一模一样的糖果🍬放在m个相同的盘子中，有多少种放法，允许盘子有空余，但不允许没放完。而集合划分就等同于将n个彼此互不相同的糖果🍬🍭🎂（因为集合中的元素不允许重复）放在m个相同的盘子中，有多少种放法，同样允许盘子空余，不允许放不完。