[AcWing 900] 整数划分

本文主要是介绍[AcWing 900] 整数划分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

类比完全背包 复杂度 \(O(n^{2})\)

总体复杂度 \(1000^{2} = 1 \times 10^{6}\)

#include<iostream>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];

int main()
{
	cin >> n;
	f[0] = 1;
	for (int i = 1; i <= n; i ++)
		for (int j = i; j <= n; j ++)
			f[j] = (f[j] + f[j - i]) % mod;
	cout << f[n] << endl;
	return 0;
}

1. 状态表示
   \(f[i][j]\) 表示从数字 \(1\) ~ \(i\) 中选，且总和等于 \(j\) 的选法数量
2. 状态转移
   类比完全背包的优化方式
   $ f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i] + \cdots $ ，
   $ f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2i] + \cdots $ ，
   可以得到 $ f[i][j] = f[i - 1][j] + f[i][j - i] $

这篇关于[AcWing 900] 整数划分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！