求解整数拆分问题

墨蓝 2023-10-11 16:35 55阅读 0赞

求将正整数n无序拆分成最大数为k的拆分方案个数，要求所有的拆分方案不重复。

例如：设n=5,k=5 对应的拆分方案如下：

（1）5=5

（2）5=4+1

（3）5=3+2

（4）5=2+2+1

（5）5=2+1+1+1

（6）5=1+1+1+1+1

思想分析：

拆分按照因子从大到小排列，每一次拆分都可视为问题规模的减少，所以可以使用递归解决思想，进而想到动态规划的写法，两种写法类似。

设q(n,m)为整数n使用不大于m的整数进行拆分的所有情况总数，因此有

1）当n==m时

可以分为两种情况，一是使用n本身，只有一种情况。二是使用不大于n-1的整数进行拆分。

所以此时q(n,m)=1+q(n,n-1)；

2）当n<m时

使用比n大的数进行拆分没有意义，所以此时q(n,m)=q(n,n)，即当前的的拆分总数等于上一次拆分总数。

3）当n>m时

这时候有两种情况，一个是使用m对n进行拆分，一个是使用小于m的数对n进行拆分

对于第一种，使用m对n进行拆分，所以拆分出来的情况最大的数是m，剩下的所有数加起来为n-m，问题变成使用不大于m的整数对n-m进行拆分，所以此时为q(n-m,m)

对于第二种，使用小于m的数对n进行拆分，即为q(n,m-1)

4）当n==1或者m==1时 只有一种情况，返回1。

**注意，这里可能会漏掉m==1的情况，这种情况是存在的。**

代码实现（动态规划）：

#include<bits/stdc++.h>
     #define maxn 100
     long dp[maxn][maxn];
     using namespace std;
     void split(int n,int k)
     {
     	for(int i=1;i<=n;i++)
     	{
     		for(int j=1;j<=k;j++)
     		{
     			if(i==1||j==1)
     			{
     				dp[i][j]=1;
    			 }
    			 else if(i<j)
    			 {
    			 	dp[i][j]=dp[i][i];
    			 }
    			 else if(i==j)
    			 {
    			 	dp[i][j]=dp[i][j-1]+1;
    			 }
    			 else
    			 {
    			 	dp[i][j]=dp[i][j-1]+dp[i-j][j];
    			 }
    		 }
    	 }
     }
     int main()
     {
     	long n,k;
     	cin>>n>>k;
     	memset(dp,0,sizeof(dp));
     	split(n,k);
     	cout<<dp[n][k]<<endl;
      }

代码实现（递归）：

#include<bits/stdc++.h>
    #define maxn 1000
    using namespace std;
    int dp[maxn][maxn];
    int split(int n,int k)
    {
    	if(dp[n][k]!=0)
    		return dp[n][k];
    	if(n==1||k==1)
    	{
    		dp[n][k]=1;
    		return dp[n][k];
    	}
    	else if(n<k)
    	{
    		dp[n][k]=split(n,n);
    		return dp[n][k];
    	}
    	else if(n==k)
    	{
    		dp[n][k]=split(n,k-1)+1;
    		return dp[n][k];
    	}
    	else
    	{
    		dp[n][k]=split(n,k-1)+split(n-k,k);
    		return dp[n][k]; 
    	}
    }
    int main()
    {
    	int n,k;
    	cin>>n>>k;
    	memset(dp,0,sizeof(dp));//初始化 
    	cout<<split(n,k);
    }