整数划分

题目描述：

一个正整数n可以表示成若干个正整数之和，如： n = n 1 + n 2 + n 3 + . . . + n k n = n_1 + n_2 + n_3+…+n_k n=n1​+n2​+n3​+…+nk​ 其中 n 1 ≥ n 2 ≥ . . . ≥ n k n_1≥n_2≥…≥n_k n1​≥n2​≥…≥nk​,问n存在多少种不同的划分方式

思路：

动态规划的计数问题

由于一个数字可以用很多次，所以我们可以把这个问题看成一个完全背包问题

$dp[i][j]$表示前i个数字构成数字和为j的划分方式的数量

状态转移为：

$dp[i][j]=dp[i-1][j]+dp[i-1][j-i]+dp[i-1][j-2\ast i]+\dots +dp[i-1][j-k\ast i]$

直接暴力进行转移就行，复杂度是 O ( n 2 l o g n ) O(n^2log_n) O(n2logn​)

考虑进行优化：

由于 $dp[i][j-i]=dp[i-1][j-i]+dp[i-1][j-2\ast i]+\dots +dp[i][j-k\ast i]$

可以发现， $dp[i][j]=dp[i-1][j]+dp[i][j-i]$

还可以再进一步压缩空间，即用完全背包的方法来优化掉第一维

#includeusing namespace std;#define endl '\n'#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)#define m_p(a, b) make_pair(a, b)typedef long long ll;typedef pair<int, int> pii;#define MAX 100005#define mod 1000000007int n, m, x, k, y, r;int tr[MAX];ll dp[1005];void work(){cin >> n;dp[0] = 1;for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){(dp[j] += dp[j - i])%=mod;}}cout << dp[n] << endl;}int main(){io;work();return 0;}

康复训练的第好几天，本来dp就不怎么会，半年不写题，全忘了，md