900. 整数划分
2021/4/11 10:57:05
本文主要是介绍900. 整数划分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
将正整数 \(n\) 表示成一系列正整数之和,\(n=n_1+n_2+…+n_k\),其中 \(n_1 \geq n_2 \geq …\geq n_k \geq 1,\ k \geq 1\)。正整数 \(n\) 的这种表示称为正整数 \(n\) 的划分。正整数 \(n\) 的不同的划分个数正整数\(n\)的划分数。
解法一
思路:有 种物品,物品的体积分别为 ,每种物品可以用无限次,求恰好装满容量为 的背包的方案数。于是,该题就转化为求完全背包的方案数。
#include <iostream> #include <algorithm> 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; }
解法二
状态: 表示和为 ,个数为 的方案的个数。
在这种状态表示下,状态转移就比较难想了。
- 的所有方案中最小值是 :
- 的所有方案中最小值大于 :
故状态转移方程:
#include <iostream> #include <algorithm> using namespace std; const int N = 1010, mod = 1e9 + 7; int n; int f[N][N]; int main() { cin >> n; f[0][0] = 1; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= i; j ++ ) f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod; int res = 0; for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod; cout << res << endl; return 0; }
这篇关于900. 整数划分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行