整数划分问题
问题定义:
给出总和n,n>=0,需要将其拆分为m个数的和,这m个数均大于等于0,例如给出n=7,m=3,有如下的拆分方式:(0,0,7),(0,1,6),(0,2,5),(0,3,4),(1,1,5),(1,2,4),(1,3,3),(2,2,3),共8种拆分方式,拆分方式之间是不考虑顺序的,即(1,1,5)和(5,1,1)是同一种拆分方式。
实际上可以再形象化的描述:给出n个苹果,放入m个盘子中,共有多少种放法。
一个经典的问题,可以先从递归的角度考虑:
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int f(int x,int y){
if(x == 0) return 1;//没有苹果,全部盘子为0,即一种放法
if(y == 0) return 0;//没有盘子,没法放,0种放法
if(y > x){//盘子数大于苹果数,至多只能x个盘子上都放一个
return f(x,x); //这里是y>x,而不是大于等于,若带上等于就会f(x,x)无限循环,
//每次递归时参数没有发生变化,所以不能带等于
}
return f(x - y, y) + f(x, y - 1);//盘子数小于等于苹果数 -> 分类讨论: 有盘子为空,没有盘子为空
//有盘子为空的时候即至少有一个盘子为空,f(x,y-1);没有盘子为空即最少每个盘子都有一个,f(x-y,y)
}
int main(){
int t,n,m;//n个苹果分到m个盘子里去,运行盘子为空
cin >> t;
while(t --){
cin >> n >> m;
cout << f(n,m) << endl;
}
return 0;
}
作者:Safe_Sound
链接:https://www.acwing.com/solution/content/8444/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
沿着上面的思路,可以发现如果把过程中的各种状态记录下来效率会更高,将其转化为dp:
#include <iostream>
using namespace std;
int f[15][15];
int main()
{
int t,m,n;
cin>>t;
for(int i=0;i<=10;i++)//苹果个数
for(int j=0;j<=10;j++)//盘子个数
{
if(i==0)f[i][j]=1; //没有苹果,只有一种放法
else if(j==0)f[i][j]=0; //没有盘子,没有放法
else if(j>i)f[i][j]=f[i][i];
//苹果数小于盘子数,一定有y-i个盘子用不上,因此f[i][j]=f[i][i]
else f[i][j]=f[i][j-1]+f[i-j][j];
}
while(t--)
{
cin>>m>>n;
cout<<f[m][n]<<endl;
}
return 0;
}