DFS

将数字 $n$ 分成 $k$ 份，即求 $x_1 + x_2 + … + x_k = n$ 的解，和 842. 排列数字 类似，可以逐一枚举 $x_i$，不做任何优化，每个位置枚举 $1 \sim n$。但题中说明 $1, 1, 5$，$1, 5, 1$ 和 $5, 1, 1$ 算同一组解，即求解的是组合数，而非排列数。可将路径保存到 set，再把可行解保存到 unordered_set，最后输出可行解个数，但这样显然多走了太多无用分支，复杂度是 $O(n^k)$

考虑如何剪枝，由于一组数字的排序（假设从小到大）是唯一的，因此我们可以以不递减顺序枚举，即让 $x_i >= x_{i-1}$，也就是下界是 $x_{i-1}$

再考虑缩小上界，我们枚举到 $x_i$ 时，它不能超过 $m = n - (x_1 + x_2 + … + x_{i-1})$。又由于 $x_i$ 是 $x_{i} \sim x_k$ 中最小的数，由于和是固定的，$x_i$ 不能超过它们的平均数，否则后面的数都会超过平均数，和就会超过 $m$

于是我们有了剪枝后的代码

#include <iostream>

using namespace std;

int n, k, ans;

void dfs(int u, int prev, int m) {
    if (u == k) {
        if (m >= prev) ans ++;
        return;
    }

    for (int i = prev; i <= m / (k - u + 1); i ++)
        dfs(u + 1, i, m - i);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> k;

    dfs(1, 1, n);

    cout << ans << '\n';

    return 0;
}

由于乘法比除法快，考虑将上界转为乘法。当枚举到 $x_i$ 时，$m = x_i + x_{i+1} + … +x_k$，$x_i$ 要取最大，则 $x_{i+1} \sim x_k$ 要尽可能小，它们最小也要等于 $x_i$，所以 $x_i <= m - (k - i) * x_i$，则有以下代码

void dfs(int u, int prev, int m) {
    if (u == k) {
        if (m >= prev) ans ++;
        return;
    }

    for (int i = prev; i <= m - (k - u) * i; i ++)
        dfs(u + 1, i, m - i);
}

递归子问题

记 $f(n, k)$ 是把 $n$ 分解为 $k$ 个数的和的所有分法

有两种情况

1. 这 $k$ 个数至少包含一个 $1$
2. 这 $k$ 个数都大于 $1$

对于计数类问题，要求划分出的子问题不重不漏，上述分法满足条件

这种划分标准在基础课讲过，见 900. 整数划分

1. 对于情况 $1$，我们可以找到一个 $1$，把它去掉，则问题等价于把 $n - 1$ 分解为 $k - 1$ 个数和，即 $f(n - 1, k - 1)$

2. 对于情况 $2$，我们可以把 $k$ 个数每个都减去 $1$，则问题等价于把 $n - k$ 分解为 $k$ 个数的和，即 $f(n - k, k)$

原问题的解等于两个子问题解的和，即 $f(n, k) = f(n - 1, k - 1) + f(n - k, k)$

考虑递归出口

1. 当 $n < k$ 时，无法划分，$f(n, k) = 0$
2. 当 $n = k$ 时，只能分成 $k$ 个 $1$，$f(n, k) = 1$
3. 当 $k = 1$ 时，只能分成 $1$ 个 $n$，$f(n, k) = 1$

于是有如下代码

#include <iostream>

using namespace std;

int resolve(int n, int k) {
    if (n < k) return 0;
    if (n == k || k == 1) return 1;

    return resolve(n - 1, k - 1) + resolve(n - k, k);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, k; cin >> n >> k;

    cout << resolve(n, k) << '\n';

    return 0;
}

最优 DP

我们用闫氏 DP 分析法过一遍流程：DP 是在有限集求最优解或合法解数，即方案数有限，但通常为指数级

状态表示，化零为整

即从逐个枚举到每次求一个集合

集合

将整数 $i$ 划分为 $j$ 个数的和的所有分法

属性

集合元素个数，$f[i, j]$ 表示将整数 $i$ 划分为 $j$ 个数的和的所有分法的数量

答案

$f[n, k]$

状态计算，化整为零

即把集合划分为若干子集，寻找原问题和子问题的递推关系，再从初始条件递推到原问题

划分

计数类 DP 要求不重不漏。每个子问题又可分为变化的部分和不变的部分

1. 最小数字等于 $1$。这类划分，不变的部分是每个划分都至少含有一个 $1$，变化的部分是除去一个 $1$ 后的 $j - 1$ 个数，去掉不变的部分，问题等价于 $f[i - 1, j - 1]$
2. 最小数字大于 $1$。这类划分，不变的部分是划分中的每个数都能写成 $1 + x$，变化的部分是 $x$，则每个数都去掉不变的 $1$ 后问题等价于 $f[i - j, j]$

条件

$j <= min(i, k)$

初始

$f[0, 0] = f[i, 1] = 1, i >= 1$

$f[0, i] = f[i, 0] = 0, i >= 1$

#include <iostream>

using namespace std;

const int N = 210, M = 10;

int f[N][M];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, k; cin >> n >> k;

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++) f[i][1] = 1;

    for (int i = 1; i <= n; i ++)
        for (int j = 2; j <= min(i, k); j ++)
            f[i][j] = f[i - 1][j - 1] + f[i - j][j];

    cout << f[n][k] << '\n';

    return 0;
}

记忆化搜索

把上面两种方法组合，就变成记忆化搜索

#include <cstring>
#include <iostream>

using namespace std;

const int N = 210, M = 10;

int f[N][M];

int dfs(int i, int j) {
    if (i < j) return 0;

    auto& fij = f[i][j];
    if (~fij) return fij;

    return fij = dfs(i - 1, j - 1) + dfs(i - j, j);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, k; cin >> n >> k;

    memset(f, -1, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++) f[i][1] = 1;

    cout << dfs(n, k) << '\n';

    return 0;
}

完全背包

问题可转化为以下完全背包问题：

有 $n$ 种物品和一个容量是 $n$ 的背包，每种物品有无限件可用，第 $i$ 种物品的体积是 $i$。求解用 $m$ 件物品装满背包的所有方法

再用闫氏 DP 分析法过一遍流程：DP 是在有限集求最优解或合法解数，即方案数有限，但通常为指数级

状态表示，化零为整

即从逐个枚举到每次求一个集合

集合

只从前 $i$ 种物品选 $k$ 件，且体积等于 $j$ 的所有选法

属性

集合元素个数，$f[i, j, k]$ 表示只从前 $i$ 种物品选 $k$ 件，且体积等于 $j$ 的所有选法的个数

答案

$f[n, n, m]$

状态计算，化整为零

即把集合划分为若干子集，寻找原问题和子问题的递推关系，再从初始条件递推到原问题

划分

计数类 DP 要求不重不漏。每个子问题又可分为变化的部分和不变的部分。通常把最后一次不同作为划分标准，此处为选几件第 $i$ 种物品

前 $i$ 种要选 $k$ 件，则第 $i$ 种可以选 $l$ 件，这些选法不变的部分是选了 $l$ 件物品 $i$，变化的部分是要从前 $i - 1$ 种物品选 $k - l$ 件，使体积等于 $j - l * i$

则 $f[i, j, k] = \sum_{l=0}^{k} f[i - 1][j - l * i][k - l]$

条件

$0 <= k <= min(n, m), 0 <= l <= k, l \times i <= j$

初始

$f[0][0][0] = 1$

则有如下朴素写法

#include <iostream>

using namespace std;

const int N = 210, M = 10;

int f[N][N][M];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, m; cin >> n >> m;

    f[0][0][0] = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
            for (int k = 0; k <= min(n, m); k ++)
                for (int l = 0; l <= k && j >= l * i; l ++)
                    f[i][j][k] += f[i - 1][j - l * i][k - l];

    cout << f[n][n][m] << '\n';

    return 0;
}

状态优化

> f[i][j][k] = f[i-1][j][k] + f[i-1][j-i][k-1] + f[i-1][j-2i][k-2] + f[i-1][j-3i][k-3] + ...
> f[i][j-i][k-1] =            f[i-1][j-i][k-1] + f[i-1][j-2i][k-2] + f[i-1][j-3i][k-3] + ...
> f[i][j][k] = f[i-1][j][k] + f[i][j-i][k-1]

于是有

#include <iostream>

using namespace std;

const int N = 210, M = 10;

int f[N][N][M];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, m; cin >> n >> m;

    f[0][0][0] = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
            for (int k = 0; k <= min(n, m); k ++) {
                f[i][j][k] = f[i - 1][j][k];
                if (j >= i && k >= 1)
                    f[i][j][k] += f[i][j - i][k - 1];
            }

    cout << f[n][n][m] << '\n';

    return 0;
}

空间优化

$f[i]$ 只依赖 $f[i]$ 和 $f[i - 1]$，可去掉第一维，同时判断也能合并到循环里

#include <iostream>

using namespace std;

const int N = 210, M = 10;

int f[N][M];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n, m; cin >> n >> m;

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
            for (int k = 1; k <= m; k ++)
                f[j][k] += f[j - i][k - 1];

    cout << f[n][m] << '\n';

    return 0;
}