整数划分问题---动态规划、递归

第一：

将一个整数 n 划分为 不超过m 组 的划分数 如  n=4 m=3 输出： 4 { 1+1+2=1+3=2+2=4} 思路：使用动态规划： 定义状态： dp[i][j] j的i划分的组数 递推：dp[i][j]=dp[i][j-i]+dp[i-1][j] ------当m=n时，变成了常见的整数划分问题

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+10;
int dp[maxn][maxn],n,m;
void sovle(){
	dp[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			if(j-i>=0){
				dp[i][j]=dp[i][j-i]+dp[i-1][j];
			}
			else dp[i][j]=dp[i-1][j];
		}
	}
	
}
int main()
{
	memset(dp,0,sizeof(dp));
	n=4;m=4;
	sovle(); 
	cout<<dp[m][n]<<endl;
}
           

第二：

我们用递归+记忆化的方法来解决普通整数划分问题：定义 f(n,m)为将整数n划分为一系列整数之和，其中加数 最大不超过m。 得到下面的递推关系式：  当n==1 || m==1 只有一种划分，即 1 或者 1+1+1......+1 当m>n 显然，等价于 f(n,n) 当m==n 此时：我考虑加数包含m与否的两种情况： 1）划分不包含m，即f(n,m-1)---所有m-1的划分 2)划分包含 m，此时只有一种即 m 所以当m==n时，有 f(n,m)=f(n,m-1)+1 当m<n时， 1）包含m时，{m,x1,x2,x3....xi}此时 等价于 f(n-m,m) 2）不包含m时，显然f(n,m-1) 所以f(n,m)=f(n,m-1)+f(n-m,m) 采用记忆化技术优化复杂度：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000+10;
int f[maxn][maxn];
int  getspilit(int n,int m)
{
	if(n==1||m==1)return 1;
	if(m>n){
		if(f[n][m]!=-1)return f[n][m];
		return f[n][m]=getspilit(n,n);
	}
	if(n==m){
		if(f[n][m]!=-1)return f[n][m];
		return f[n][m]=getspilit(n,m-1)+1;
	} 
	return f[n][m]=(getspilit(n-m,m)+getspilit(n,m-1));
}
int main()
{
	int n=4,m=4;
	memset(f,-1,sizeof(f));
	cout<<getspilit(n,m)<<endl;
	return 0;
}
           

第三：

将整数n划分为一系列连续的整数之和即： 15=7+8     =4+5+6     =1+2+3+4 这里我们假设划分之后最小的整数位x ，那么 x+(x+1)+(x+2)......+(x+m)假设一共有i个整数，整理得： x*i+i*(i-1)/2=n i=1,2,3.....其中i的限制条件为：s1=i*(i-1)/2<=n，只有当x为整数时才有可能。

#include<iostream>
#include<cstring>
using namespace std;
int getsplit(int n)
{
	int i,s1,s2,x,sum=0;
	for(i=1;(s1=i*(i-1)/2)<=n;i++)
	{
		s2=n-s1;
		x=s2/i;
		if(x==0)break;
		if(s2%i==0)
		{
			cout<<x<<" ";
			for(int j=1;j<i;j++)cout<<x+j<<" ";
			cout<<endl;
			sum++;
		}
	}
	return sum;
}
int main()
{
	int n=15;
	cout<<getsplit(n)-1<<" methods to split the number."<<endl;
}