type
status
date
slug
summary
tags
category
icon
password
Property
Mar 4, 2023 02:36 AM
这道题困扰了我整整三天，记录一下 😅
输入样例:
5
输出样例：
7
要注意的一点是，这里边的划分，与顺序是没有关系的！例如5的划分2 + 3 和3 + 2 算作同一种划分~
思路一：
把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）
初值问题：
求最大值时，当都不选时，价值显然是 0
而求方案数时，当都不选时，方案数是 1（即前 i 个物品都不选的情况也是一种方案），所以需要初始化为 1,
f[0][0] = 1
等价变形后： f[0] = 1状态计算：
f[i][j]表示前i个整数（1,2…,i）恰好拼成j的方案数
求方案数：把集合选0个i，1个i，2个i，…全部加起来
因此
f[i][j]= f[i−1][j] + f[i][j - i] (这一步类似完全背包的推导）朴素做法
优化版：
一点小小的个人思考：
完全背包解法中，状态转移方程为
f[i][j] = f[i - 1][j] + f[i][j - i]- 为什么要加上
f[i - 1][j]，f[i][j - i]? 因为对于j,1~i - 1可以组成j的个数，显然也是1~i组成j的个数的一部分; 对于f[i][j - i]，只要再加上一个i就可以成为f[i][j]
- 为什么不加
f[i - 2][j],f[i - 3][j]…? 因为他们f[i - 2][j]包含在f[i - 1][j]中，f[i - 3][j]包含在f[i - 2][j]中
- 为什么不加
f[i][j - 2*i]..? 同上，f[i][j - 2*i]无法一步直接到f[i][j]，而f[i][j - 2*i]已经包含在f[i][j - i]中
- 为什么不加
f[i][j - 1]…? 以f[i][j - 1]为例，将组合情况中最后的一个1移到最前面，可以发现，其实f[i][j - i]已经包含了这种情况
思路二：
状态表示：
f[i][j]表示总和为 i ，总个数为 j 的方案数状态转移方程：
f[i][j] = f[i - 1][j - 1] + f[i - j][j]代码：
- 作者:GJJ
- 链接:https://blog.gaojj.cn/article/blog-06
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。