计数动态规划

整数划分

现在给定一个正整数 $n$，请你求出 $n$ 共有多少种不同的划分方法。

显然可以看作是 $1n$ 之间的一种背包问题。正整数 $n$ 是一个容量为 $N$ 的背包，有 $n$ 件物品，物品的体积分别是 $1n$，我们求的是 恰好装满背包 的可行数，每个物品可以用无限次 —— 完全背包。

• 状态表示：
  • 集合：f[i][j] 表示从 $1\sim i$ 中选，总体积恰好是 $j$ 的选法
  • 属性：选法的数量
• 状态计算：
  • 一个第 $i$ 个物品都不选 f[i-1][j]
  • 至少选择 1 个第 $i$ 个物品 f[i][j-i]
  • 转移方程：f[i][j] = f[i-1][j] + f[i][j-i]
  • 化为一维：f[j] = f[j] + f[j - i]

AC900. 整数划分

核心代码：

// ...
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (j >= i) {
                f[j] += f[j - i];
            }
            
            f[j] %= m;
        }
    }

稍微优化一下：

// ...
    for (int i = 1; i <= n; i ++) {
        for (int j = i; j <= n; j ++) {
            f[j] += f[j - i];
            f[j] %= m;
        }
    }

另外一种方法：

• 状态表示：
  • 集合：所有总和是 $i$，且恰好表示成 $j$ 个数的和的方案
  • 属性：数量
• 状态计算：
  • 最小值是 1：f[i-1][j-1] 与 f[i][j] 数量相同
  • 最小是大于 1：把里面的 $j$ 个数都减去 1，得到的还是一个方案，和为 $i-j$，因此是 f[i-j][j]
  • 方程：f[i][j] = f[i-1][j-1] + f[i-j][j]

对比两个状态转移方程：

f[i][j] = f[i - 1][j] +     f[i][i - j];
f[i][j] = f[i - 1][j - 1] + f[i - j][j];

• 第一个方程由正上方和正左边转移过来
• 第二个方程由斜上方和正上方转移过来
• 注意到：下面得到的 f[i][j] 需要求和，也就是 f[n][0]~f[n][n] 求和结果才是方案

AC900. 整数划分