AcWing 900. 整数划分

题意：

将正整数n分解为若干个正整数的和，问有多少种组合

做法 （我发现的就有4种）

算法1. f[i][j] 表示前面$i$个数的和是$j$的方案数

其实就是完全背包的变形题
可以将题意转化为：有 $1, 2, \ldots, n$ 这n个物品，每个物品都可以选无数次，问选出来的物品的体积之和恰好为$n$的方案数

状态转移： f[i][j] = f[i][j - i] + f[i - 1][j]

扩展：若每个数字均要求互不相同，则问题变为 0-1背包

扩展：第一维i从小到大遍历求的是组合数，若求排列数就只能第一维j从小到大遍历

算法2. f[i][j] 表示任意$i$个正整数的和是$j$的方案数

注意与【算法1】的区别，他是考虑前i个数中选数，但是选的个数不一定是i，【算法2】是一定选i个数，不一定是从前i个数中选择

具体分析见下图（不得不说这种f[i][j]集合划分方式真是神之一手）

算法3. f(n, m) 表示每个数都不超过m，且和为n的方案数

这个留着以后补充吧，递推方程也挺简单想的到的

算法4. dfs brute force