鏈接：https://vjudge.net/problem/OpenJ_Bailian-4119
思路：這個(gè)題一共有三個(gè)小問，均可以用同一個(gè)類似的狀態(tài)轉(zhuǎn)移，即如果分的數(shù)里面有1，則減去1猖任，如果沒有，則減去數(shù)字的個(gè)數(shù)（相當(dāng)于每個(gè)數(shù)減一），從而有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表示相加數(shù)字的個(gè)數(shù)總和
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表示相加數(shù)字的個(gè)數(shù)總和的上限
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的意思同第二個(gè)
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;
}
