链接：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;
}
