C/C++教程

[AcWing 900] 整数划分

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

image

类比完全背包 复杂度 \(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] 整数划分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航