OpenJudge(复杂整数的划分问题)

链接：https://vjudge.net/problem/OpenJ_Bailian-4119
思路：这个题一共有三个小问，均可以用同一个类似的状态转移，即如果分的数里面有1，则减去1，如果没有，则减去数字的个数（相当于每个数减一），从而有dp[i][j]=dp[i-j][j]+dp[i-1][j-1]

代码：

#include<iostream>
#include<cstring>
using namespace std;

const int maxn = 51;
int n,k;
long long int dp1[maxn][maxn],dp2[maxn][maxn],dp3[maxn][maxn];

int main(){
    while(cin>>n>>k){
   
    memset(dp1,0,sizeof(dp1));
    for(int i=1;i<=n;i++){
        dp1[i][1] = 1;
    }

//这里的j表示相加数字的个数总和
    for(int i=1;i<=n;i++){
        for(int j=2;j<=i;j++){
            dp1[i][j] = dp1[i-j][j] + dp1[i-1][j-1];
        }    
    }

//这里j表示相加数字的个数总和的上限
    memset(dp2,0,sizeof(dp2));
    dp2[0][0] = 1;
    for(int i=0;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j<=i)dp2[i][j] = dp2[i-j][j-1]+dp2[i][j-1];
            else dp2[i][j] = dp2[i][i];
        }
    }

//这里j的意思同第二个
    memset(dp3,0,sizeof(dp3));
for(int i=0;i<=n;++i)
    {
        dp3[i][1]=1;        
        if(i&1)dp3[0][i]=1;
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j&1)
            {
                if(j<=i)dp3[i][j]=dp3[i-j][j]+dp3[i][j-1];
                else dp3[i][j]=dp3[i][i];
            }
            else dp3[i][j]=dp3[i][j-1];
        }
    }
    cout<<dp1[n][k]<<endl<<dp2[n][n]<<endl<<dp3[n][n]<<endl;
    }
    return 0;
}