题解 | #数的划分#

NC152 数的划分

题意

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不能相同(不考虑顺序)，求方案数，对1e9+7取模。

1. 暴力法（效率很低，数字大了会tle）

我们分析下样例的规律：

n=7, k=3
[1,1,5]
[1,2,4]
[1,3,3]
[2,2,3]

直接使用回溯法，暴力枚举每一位数字，需要注意以下规律：

当前位置的最小数字要>=上一位数字
当前位置的最大数字要<=下一位数字（要留出足够大的数给下一位）

算法基于深度优先搜索，用全局变量记录搜索树的路径和答案数目。

以样例为例，搜索树的过程如下图所示（异常分支简略表示）：

图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */
    int k, res;
    const int M = 1e9 + 7;
    int divideNumber(int n, int k2) {
        // 把k赋值到一个全局变量        
        k = k2, res = 0;

        // 从第一层开始搜索, 还剩下可分配的数是n, 本层最小的一个待尝试的数是1
        dfs(1, n, 1);

        return res;
    }

    void dfs(int depth, int rest, int start) {
        // 如果k层都搜完了
        if (depth == k+1) {
            // 恰好没有剩余可分配的数
            if (rest == 0) {
                res++; // 搜到第k+1步，说明找到一个解
                res %= M;
            }
            return;
        }

        // 最小的数是start，最大的数是rest，继续向下深搜
        for (int i = start; i <= rest; i++) {
            // 层数+1， 剩余的数是rest-i，下一层最小待尝试的数是i
            dfs(depth+1, rest-i, i);
        }
    }
};

时间复杂度： $O(k!)$ , 一共有k层递归，每层递归中，有当前层数减一轮循环遍历。考虑到k极小，所以能过。 2021.8.6 update: k增强到5000, 所以会tle.
空间复杂度： $O(k)$ , 一共有k层递归，每层的空间为O(1).

2. 动态规划

观察问题的规律，我们可以发现问题可以拆分成子问题，并且子问题具有独立性，如果把总问题看做f[n][k], 那么每次确定了一个数j，则问题规模缩小为f[n-j][k-1]，且二者是独立的. 因此我们可以利用动态规划的性质，解决此题。

令dp[i][j]表示把数字i分成j份的方案数。

考虑 $i>=j$ 和 $i<j$ 两种情况：

i<j, 无解. 因为每一份至少是1.
i==j, 1种方案。
i>j. 先把每一份都分配上1，剩下的i-j可以分配给0份，1份，2份。。。。。。j份，故有如下公式：

$dp[i][j] = \sum_{k=1}^jdp[i-j][k]$

这个东西有点像前缀和，我们往前写一项：

$dp[i-1][j-1] = \sum_{k=1}^{j-1}dp[(i-1)-(j-1)][k] = \sum_{k=1}^{j-1}dp[i-j][k]$

两式做差得：

$dp[i][j] = dp[i-1][j-1]+dp[i-j][j]$

实现之, 最后 $dp[n][k]$ 即为答案。

2021.8.6 update: 数据范围提高到5000,1000,题面改为对1e9+7取模,更新ac代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 被划分的数
     * @param k int 化成k份
     * @return int
     */

    // n <= 5000, k <= 1000
    static const int N = 5010, K = 1010;
    static const int M = 1e9 + 7;
    int dp[N][K];
    int divideNumber(int n, int k) {
        // 初始化所有的数组值为0
        memset(dp, 0, sizeof(dp));

        // i==j的情况只有一种方案
        for (int i = 0; i <= k; i++) {
            dp[i][i] = 1;
        }

        // i>j的情况
        for (int i = 1; i <= n; i++) 
            // 这里需要同时满足j <= k和 j <= i, 因为j>i就没意义了
            for (int j = 1; j <= min(k, i); j++)
                dp[i][j] = (dp[i-1][j-1] + dp[i-j][j]) % M;

        return dp[n][k];
    }
};

时间复杂度: $O(nk)$ . 有两重循环。
空间复杂度： $O(nk)$ . 开了 $n*k$ 大小的二维数组。