LeetCode 1420. 生成数组

2021-03-18 HGNULB 约 8 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1420. 生成数组

题意分析

题目给了一段求最大值的伪代码：从左到右扫描数组，遇到比当前记录的最大值更大的元素就更新，并把 search_cost 加一。现在要问：长度为 n、每个元素取值在 [1, m] 的数组中，有多少个数组跑完这段伪代码后 search_cost 恰好等于 k？答案对 $10^9 + 7$ 取模。

先把 search_cost 的含义翻译清楚：它统计的是扫描过程中「当前最大值被刷新」的次数，也就是数组的严格前缀最大值的个数。第一个元素必然刷新一次（初始最大值是 0，任何 [1,m] 的值都比它大），所以 search_cost 至少是 1。

由此得到两个立即可用的推论。第一，k = 0 时答案必然是 0（长度至少为 1，第一次必刷新）。第二，search_cost 最多是 n（每个位置都刷新，此时数组严格递增），也不可能超过 m（值域只有 m 个不同的值，严格递增最多 m 项）。

关键的观察是：search_cost 只和「哪些位置刷新了最大值」有关，与非刷新位置的具体取值无关——非刷新位置只要不超过当前最大值就行。这提示状态里需要携带「当前最大值」和「已刷新次数」两个信息，而不需要记住整个数组。

约束里 n、m 最大 50，k 最大 min(n, m)。三者相乘只有 $1.25 \times 10^5$ 量级，说明 $O(nmk)$ 的三层状态是被允许的；但如果转移里再套一层枚举变成 $O(nm^2k)$，也才 $6 \times 10^6$，其实同样能过。不过前缀和优化是这类题的标准手法，值得按最优写法掌握。

边界要留意四点：k = 0 返回 0；k > m 或 k > n 时答案为 0（代码里会自然算出 0）；方案数是指数级的，全程必须取模；n = 1 时答案是 m（任何单元素数组的 search_cost 都是 1）。

解法：DP + 前缀和优化

核心思路

枚举全部 $m^n$ 个数组不可行。扫描一个前缀后，未来转移只关心两个量：当前最大值，以及最大值被刷新了多少次；前缀的具体排列不再影响后续选择。

对当前长度 len，定义 dp[maximum][cost]：最大值恰好为 maximum、搜索代价恰好为 cost 的数组数量。单元素数组 [maximum] 会第一次刷新最大值，因此初始状态是 dp[maximum][1] = 1。

在末尾追加一个数并得到新最大值 maximum 时只有两类互斥情况：

新数不超过 maximum：有 maximum 种取值，最大值和代价不变，贡献 maximum * dp[maximum][cost]。

新数就是 maximum 且刷新了最大值：旧最大值 p 必须满足 p < maximum，旧代价为 cost - 1，贡献所有这类状态之和。

因而转移为
\[next[maximum][cost] = maximum \cdot dp[maximum][cost] + \sum_{p=1}^{maximum-1} dp[p][cost-1]\]
第二项若逐状态求和会多一层 m。固定 cost 后按 maximum 从小到大扫描，用 smaller 维护当前之前的前缀和。计算 next[maximum][cost] 时，smaller 恰好等于上式的求和；计算完成后再把 dp[maximum][cost-1] 加入，供下一个最大值使用。

正确性可按长度归纳：初始层准确；任一更长数组删除末位后唯一落入“刷新”或“不刷新”之一，两个分支互斥且穷尽，前缀和只合并求和、不改变计数。因此每层 dp 都精确表示状态定义。最终对所有 maximum 的 dp[maximum][k] 求和。

解题步骤

若 k == 0、k > n 或 k > m，直接返回 0：非空数组至少刷新一次，刷新次数也不可能超过长度或值域大小。

初始化长度 1：对 maximum = 1..m，令 dp[maximum][1] = 1。

对长度 2..n 新建 next，避免原地更新污染上一层。

对每个 cost，令 smaller = 0，再按最大值升序计算“不刷新贡献 + 刷新贡献”并取模。

每算完一个最大值，把 dp[maximum][cost-1] 加入 smaller；这个先算后加的顺序保证只包含严格更小的旧最大值。

滚动 dp = next，最后汇总 dp[maximum][k]。

例如 n = 3, m = 2, k = 2。合法数组为 [1,1,2]、[1,2,1]、[1,2,2]，答案 3。其中 [1,2,2] 说明“不刷新”分支必须有 maximum 种选择，等于当前最大值也不会增加代价。

边界上，n = 1 时答案为 m 当且仅当 k = 1；k > min(n,m) 时为 0。所有加法和乘法都要取模，Java 乘法前必须转为 long。

代码实现

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numOfArrays(int n, int m, int k) {
        if (k == 0 || k > n || k > m) {
            return 0;
        }

        int[][] dp = new int[m + 1][k + 1];
        for (int maximum = 1; maximum <= m; maximum++) {
            dp[maximum][1] = 1;
        }

        for (int length = 2; length <= n; length++) {
            int[][] next = new int[m + 1][k + 1];
            for (int cost = 1; cost <= Math.min(k, length); cost++) {
                int smaller = 0;
                for (int maximum = 1; maximum <= m; maximum++) {
                    long keepMaximum = (long) dp[maximum][cost] * maximum;
                    next[maximum][cost] = (int) ((keepMaximum + smaller) % MOD);

                    smaller += dp[maximum][cost - 1];
                    if (smaller >= MOD) {
                        smaller -= MOD;
                    }
                }
            }
            dp = next;
        }

        int answer = 0;
        for (int maximum = 1; maximum <= m; maximum++) {
            answer += dp[maximum][k];
            if (answer >= MOD) {
                answer -= MOD;
            }
        }
        return answer;
    }
}

func numOfArrays(n int, m int, k int) int {
	const mod = 1_000_000_007
	if k == 0 || k > n || k > m {
		return 0
	}

	dp := make([][]int, m+1)
	for maximum := 0; maximum <= m; maximum++ {
		dp[maximum] = make([]int, k+1)
	}
	for maximum := 1; maximum <= m; maximum++ {
		dp[maximum][1] = 1
	}

	for length := 2; length <= n; length++ {
		next := make([][]int, m+1)
		for maximum := 0; maximum <= m; maximum++ {
			next[maximum] = make([]int, k+1)
		}

		for cost := 1; cost <= k && cost <= length; cost++ {
			smaller := 0
			for maximum := 1; maximum <= m; maximum++ {
				keepMaximum := int64(dp[maximum][cost]) * int64(maximum)
				next[maximum][cost] = int((keepMaximum + int64(smaller)) % int64(mod))

				smaller += dp[maximum][cost-1]
				if smaller >= mod {
					smaller -= mod
				}
			}
		}
		dp = next
	}

	answer := 0
	for maximum := 1; maximum <= m; maximum++ {
		answer += dp[maximum][k]
		if answer >= mod {
			answer -= mod
		}
	}
	return answer
}

复杂度分析

时间复杂度：$O(nmk)$。每个长度、代价和当前最大值组合只做常数次运算；运行前缀和消除了对旧最大值的额外枚举。

空间复杂度：$O(mk)$。只保留上一长度的 dp 和当前长度的 next；运行前缀和只需一个变量。

关键点总结

dp[maximum][cost] 中两个量都必须是“恰好”，否则追加元素的选择数无法确定。

不刷新时，新元素可取 1..maximum，贡献系数是 maximum。

刷新到新最大值 maximum 时，新元素已经固定，贡献是所有更小旧最大值的方案和，不再乘选择数。

smaller 在当前状态计算后再更新，才能表示严格小于 maximum 的前缀和。

长度维只依赖上一层，应使用滚动数组；计数全程取模，乘法使用 64 位中间值。

易错点总结

不刷新分支乘 maximum - 1：新元素等于当前最大值也不会刷新；n=3,m=2,k=2 会漏掉 [1,2,2]。

刷新分支包含旧最大值等于新最大值的状态：追加相等值不是刷新；必须使用严格更小的前缀和。

计算当前状态前先更新 smaller：会把 dp[maximum][cost-1] 错计进刷新分支，等价于把相等最大值当成刷新。

原地覆盖 dp：当前长度会读到本层刚写出的值，长度状态混在一起；必须写入 next。

初始化为 dp[maximum][0] = 1：非空数组第一次元素必定刷新，n=1,m=5,k=1 会被算成 0。

忽略非法 k 或乘法溢出：k=0、k>n、k>m 应返回 0；Java 的乘积必须先转为 long。

相似题目

题目	难度	考察点
629. K 个逆序对数组	困难	同为「恰好 k 个某种事件」的计数 DP，转移是连续区间求和，必须用前缀和优化
920. 播放列表的数量	困难	状态是「已用歌曲数 + 已排长度」，转移要区分新歌与重播，同属排列计数
1155. 掷骰子等于目标和的方法数	中等	按「最后一个骰子的点数」分类转移，是本题「按末位决策分类」的入门版
96. 不同的二叉搜索树	中等	按根的位置分类的计数 DP，训练「枚举最后一步」的思维
115. 不同的子序列	困难	二维计数 DP，转移按「当前字符用不用」分成两支
940. 不同的子序列 II	困难	需要用「上次出现位置」去重，展示计数 DP 中避免重复的技巧
518. 零钱兑换 II	中等	组合计数，循环顺序决定算组合还是排列，是计数 DP 必踩的坑
494. 目标和	中等	转化为子集和计数，训练把问题变形到标准背包
91. 解码方法	中等	一维计数 DP，按「最后一位单独解还是两位一起解」分类
300. 最长递增子序列	中等	转移里含 $\max_{p<j}$ 形式，可用树状数组把 $O(n)$ 压成 $O(\log n)$
368. 最大整除子集	中等	同为「从更小状态求和或取最值」的转移，还要回溯构造具体方案
887. 鸡蛋掉落	困难	状态设计需要反转视角（用操作次数反推可测层数），是状态定义训练的高阶题
312. 戳气球	困难	区间 DP，按「最后戳破哪个」分类，与本题「按最后一步分类」同源
87. 扰乱字符串	困难	多维状态的记忆化搜索，训练把复杂过程压缩成有限状态