HDU acm1028 整数划分递归问题（递推）

我们用递归+记忆化的方法来解决普通整数划分问题：定义 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<cstdio>

 #include<cstring>

 using namespace std;

 #define MAXN 130

 int num[MAXN][MAXN];

 int dp(int n,int k)

 {

     if(n==||k==)

         return ;

     if(k>n)

     {

         k=n;

         if(num[n][n]==-)

             return num[n][n]=dp(n,n);

         else

             return num[n][n];

     }

     else if(k==n)

     {

         if(num[n][k]==-)

             return num[n][k]=dp(n,k-)+;

         else

             return num[n][k];

     }

     else

     {

         if(num[n][k]==-)

             return num[n][k]=dp(n,k-)+dp(n-k,k);

         else

             return num[n][k];

     }

 }

 int main()

 {

     int n;

     while(cin>>n)

     {

         memset(num,-,sizeof(num));

         cout<<dp(n,n)<<endl;

     }

     return ;

 }

巴特西

HDU acm1028 整数划分递归问题（递推）

最新文章

热门文章

巴特西

HDU acm1028 整数划分 递归问题（递推）

最新文章

热门文章

HDU acm1028 整数划分递归问题（递推）