题目描述

给你三个整数 n、m 和 k。下面描述的算法用于找出正整数数组中最大的元素。

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++) {
    if (maximum_value < arr[i]) {
        maximum_value = arr[i];
        maximum_index = i;
        search_cost = search_cost + 1;
    }
}
return maximum_index

请你生成一个具有下述属性的数组 arr：

• arr 中有 n 个整数。
• 1 <= arr[i] <= m 其中 (0 <= i < n)。
• 将上面提到的算法应用于 arr，search_cost 的值等于 k。

返回上述条件下生成数组 arr 的 方法数，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。

样例

输入：n = 2, m = 3, k = 1
输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

输入：n = 5, m = 2, k = 3
输出：0
解释：没有数组可以满足上述条件。

输入：n = 9, m = 1, k = 1
输出：1
解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]

输入：n = 50, m = 100, k = 25
输出：34549172
解释：不要忘了对 1000000007 取余

输入：n = 37, m = 17, k = 7
输出：418930126

限制

• 1 <= n <= 50
• 1 <= m <= 100
• 0 <= k <= n

算法

(动态规划) $O(nkm)$

1. 设 $f(i, c, j)$ 表示填充了前 $i$ 个位置，search_cost 为 $c$，且最大值为 $j$ 时的方案数。
2. 初始时 $f(1, 1, j) = 1$，其余为 0。
3. 转移时，对于 $f(i, c, j)$，如果上一个位置结尾时，最大值已经为 $j$，则我们这个位置有 $j$ 种方案（即填 1 到 $j$），且不需要增加花费，可以累加 $f(i - 1, c, j) * j$。
4. 如果上一个位置结束时最大值不到 $j$，则我们需要这个位置填 $j$，即一种方案，且需要增加花费。此时可以累加 $\sum_{l=1}^{j - 1}{f(i - 1, c - 1, l)}$ 的和。
5. 我们不妨用 $g(i, c, j)$ 来表示 $f(i, c, j)$ 在第三维上的前缀和，则第二个转移就是累加 $g(i - 1, c - 1, j - 1)$。
6. 最终答案为 $g(n, k, m)$。

时间复杂度

• 状态数为 $O(nkm)$，采用了辅助数组 $g$，转移时间为常数，故总时间复杂度为 $O(nkm)$。

空间复杂度

• 需要额外 $O(nkm)$ 的空间存储状态。
• 可以通过滚动数组优化到 $O(km)$。

C++ 代码

class Solution {
public:
    #define LL long long

    int numOfArrays(int n, int m, int k) {
        const int mod = 1000000007;
        LL f[60][60][110], g[60][60][110];
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));

        for (int j = 1; j <= m; j++) {
            f[1][1][j] = 1;
            g[1][1][j] = j;
        }

        for (int i = 2; i <= n; i++)
            for (int c = 1; c <= k; c++)
                for (int j = 1; j <= m; j++) {
                    f[i][c][j] = (f[i - 1][c][j] * j + g[i - 1][c - 1][j - 1]) % mod;
                    g[i][c][j] = (g[i][c][j - 1] + f[i][c][j]) % mod;
                }

        return g[n][k][m];
    }
};