整数划分

题目描述：

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

思路：

动态规划的计数问题

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

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

状态转移为：

dp[i][j] = dp[i-1][j] + dp[i-1][j-i] + dp[i-1][j-2*i] + … + dp[i-1][j-k*i]

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

考虑进行优化：

由于 dp[i][j-i] = dp[i-1][j-i] + dp[i-1][j - 2*i] + … + dp[i][j-k*i]

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

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

#include<bits/stdc++.h>
using 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 1000000007
int 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;
}