求解整数拆分问题【动态规划】【备忘录】

问题描述

求讲正整数n无需拆分成最大数为k的拆分方案个数【f(n,k)】，要求所有的拆分方案不重复。

动态规划

f(n,k)满足动态规划问题的最优性原理、无后效性和有重叠子问题。

f(n,k):

1. 当n=1或k=1，f(n,k)=1
2. 当n<k，f(n,k)=f(n,n)
3. 当n=k，将n拆分成一个n，或者n拆分成不超过n-1的数，f(n,n)=f(n,n-1)+1
4. 当n>k，拆分中至少包含一个k，或者拆分中不包含k，f(n,k)=f(n-k,k)+f(n,k-1)

#include<bits/stdc++.h>
using namespace stdn,k;
#define MAXN 500
int dp[MAXN][MAXN];
//动态规划算法 
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];
			//printf("(%d,%d)=%d
", i, j, dp[i][j]);
		 } 
}

int main()
{
          
   
	int n=5, k=5;
	memset(dp, 0, sizeof(dp));
	Split(n, k);
	printf("(%d,%d)=%d
", n, k, dp[n][k]);
	return 0;
}

递归法/备忘录方法

备忘录方法是动态规划（自底向上）的变形，是一种自顶向下的递归方法，但当某个字问题的解求出后将结果保存在一张表(dp)中，而且相同的子问题只计算一次。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500
int dp[MAXN][MAXN];
//递归法
int dpf(int n, int k)
{
          
   
	if(dp[n][k]!=0)
		return dp[n][k];
	else if(n==1||k==1)
		dp[n][k]=1;
	else if(n<k)
		dp[n][k]=dpf(n, n);
	else if(n==k)
		dp[n][k]=dpf(n, n-1)+1;
	else 
		dp[n][k]=dpf(n, k-1)+dpf(n-k, k);
	return dp[n][k];
 } 

int main()
{
          
   
	int n=5, k=5;
	memset(dp, 0, sizeof(dp));
	printf("(%d,%d)=%d
", n, k, dpf(n, k));
	return 0;
}