复杂的整数划分

article/2025/10/7 20:26:14

复杂的整数划分

又到了动态规划的时间了！

记得我之前讲过的三要素哦

下面这一条题目其实思路并不是非常的难，但是在细节处理上要非常仔细，而且它有3个相互独立的动态规划问题。

总时间限制:
200ms
内存限制:
65536kB

描述

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。

输入
标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N)
输出
对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目
样例输入

5 2

样例输出

2
3
3

提示
第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1

其实比较简单是问题2，3，特别是问题3。
当问题2你再三琢磨，显然他是一个简单版本01背包问题，所以套路就非常明显了。

对于问题一而言的话，可能会出现看两种情况：

设计出了非常常规的子问题和状态，但是无法写出状态转移方程，或者细节遗漏
无法想出子问题

其实根据这种题目的思路，设计出状态是比较简单的，主要讲一下状态转移方程：
当然这个第一题的状态转移方程或许首次做题时候是比较难想的

//i被分成j份的拆法return dp1[i][j]=dp11(i-1,j-1)+dp11(i-j,j);//项里面至少有一个1的+没有1的

有1的容易，没有1的我建议可以通过试探的方法得出上面得结论
如果你的数字感觉比较好，那也是分分钟可以目测出来的，😝。

然而着还没有结束的哦，你要好好想一下触发上面转移方程得条件哦

下面呈现我的代码

//by Gary
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N=80;
//dp[i][j]
int dp1[N][N];  //i被分成j份的拆法
int dp2[N][N]; //前i个数凑成j的方法
int dp3[N][N];  //同2
int dp11(int i,int j)
{//初始状态和边界if(dp1[i][j]!=-1) return dp1[i][j];if(i==j||j==1||j==0) return dp1[i][j]=1;if(i==0) return dp1[i][j]=0;if(i>=j+j)return dp1[i][j]=dp11(i-j,j)+dp11(i-1,j-1);return dp1[i][j]=dp1[i-1][j-1];//全部分法当中都一定有1
}
//01背包问题 填满 w[i]=i
int dp22(int i,int j)
{if(j==0)return 1;if(i==0)return 0;if(dp2[i][j]!=-1) return dp2[i][j];//减少重复计算了int result=dp22(i-1,j);//不取iif(i<=j)result+=dp22(i-1,j-i);//取dp2[i][j]=result;return result;
}int dp33(int i,int j)
{if(j==0)return 1;if(i==0)return 0;if(dp3[i][j]!=-1)return dp3[i][j];int result=dp33(i-1,j);//不取if(i%2&&i<=j)result+=dp33(i,j-i);//可以相同dp3[i][j]=result;return result;
}
int main()
{int n,k;memset(dp1,0xff,sizeof(dp1));memset(dp2,0xff,sizeof(dp2));memset(dp3,0xff,sizeof(dp3));while(cin >> n >> k) {cout << dp11(n,k) <<endl;cout << dp22(n,n) << endl;cout << dp33(n,n) <<endl;}return 0;
}

这个代码或许确实不太美观，实在不好意思😂

当然正如我前面讲过的，状态的设置会直接决定你后面思考的难度。
后面思考难度的降低，当然也可能引起状态设置难度的上升😫

第一小题，我再提供一种别人的状态的设置

int waysNK[M][M][M]; // waysNK[i][j][k] 用 <= i的k个数，凑出和为j 
int WaysNK(int i,int j,int k) {if( j == 0 && k == 0)return 1;if( k == 0)return 0;if( j == 0)return 0;if( i == 0)return 0;if( waysNK[i][j][k] != -1)return waysNK[i][j][k];int result = WaysNK(i-1,j,k);if( j >= i) result += WaysNK(i,j-i,k-1);waysNK[i][j][k] = result;return result;}