LeetCode 1420. 生成数组
题目描述
题意分析
统计长度恰好为
n、每项取值在1到m的数组数量，要求从左到右扫描时，当前最大值恰好被刷新k次。只有遇到严格更大的元素才刷新，遇到相等或更小的元素不增加次数。数组非空且元素为正，首个元素一定刷新一次。这里统计的是有顺序的数组方案，同一批数字不同排列可能产生不同刷新次数；最终方案数对
10^9 + 7取模。
解法：DP + 前缀和优化
核心思路
[!blue]
逐个追加元素时，未来只需要知道当前最大值和已经刷新几次，不需要保留完整前缀。因此定义
dp[maximum][cost]：在当前已处理长度下，最大值恰为maximum、刷新次数恰为cost的数组数量。长度一时，每个最大值只对应单元素数组，所以dp[maximum][1] = 1。要追加一个元素得到新状态
(maximum, cost)，最后一步只有两类互斥来源：
- 不刷新最大值：旧状态已经是
(maximum, cost)，末项可以选一到maximum中任何值，共maximum种，因此贡献dp[maximum][cost] * maximum。- 刷新最大值：末项必须正好取
maximum，旧最大值严格小于它，旧刷新次数为cost - 1，因此贡献所有较小旧最大值状态的数量之和。这两类按最后一个元素是否刷新来划分，既不会重复，也覆盖每个合法数组。直接求第二类贡献会再枚举一次旧最大值，可以用递增扫描时的前缀和消掉这一层循环。
固定
cost后，从小到大枚举maximum，令smaller保存上一长度中、刷新次数为cost - 1、最大值严格小于当前位置的方案总和。先用它计算当前next[maximum][cost]，再把dp[maximum][cost - 1]加进去，供下一位置使用。这个先后顺序保证相等最大值不会被误当成一次刷新。每次增加长度都新建
next，所有来源只读取旧dp，完成整层后再替换，避免同一轮连续追加多次。计数及时取模，不刷新分支的乘法先使用 64 位，以免取模之前就溢出。刷新次数至少为一，且不超过数组长度，也不超过可用值的种数，所以
k == 0、k > n或k > m都可直接返回零。生成完整长度后，再把所有最终最大值下刷新次数恰好为k的状态相加。
解题步骤
- 排除不可能的
k，初始化长度一时各个最大值的方案数。- 逐步增加数组长度，为下一长度创建全零状态表
next。- 枚举可行刷新次数，每次将严格前缀和
smaller重置为零。- 递增枚举最大值，用“不刷新分支乘选择数 + smaller”计算当前状态并取模。
- 当前状态算完后，才将旧表中当前最大值、少一次刷新的方案加入
smaller。- 用
next替换旧表，最后汇总所有最大值对应的k次刷新方案。
代码实现
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++) {
// 每个 cost 单独累积严格更小的旧最大值。
int smaller = 0;
for (int maximum = 1; maximum <= m; maximum++) {
// 不刷新时末项有 maximum 种选择，乘法先使用 64 位。
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++ {
// 每个 cost 单独累积严格更小的旧最大值。
smaller := 0
for maximum := 1; maximum <= m; maximum++ {
// 不刷新时末项有 maximum 种选择，乘法先使用 64 位。
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)$，只保存相邻两种长度的状态表，不保存全部长度。
关键点总结
[!green]
- 最大值与刷新次数都表示恰好，不是上界。
- 不刷新时有
maximum种末项，刷新时末项固定、旧最大值严格更小。- 前缀和先使用后累加，保证只包括严格更小的旧最大值。
- 新旧长度分表，宽整数乘法和及时取模保证数值正确。
易错点总结
[!yellow]
- 把首元素的刷新次数设为零，会让全部状态偏少一次。
- 不刷新分支乘
maximum - 1会遗漏末项等于当前最大值的合法选择。- 先把当前最大值加入
smaller再计算，会把相等值也算成刷新。- 每个
cost都需要重新初始化smaller，不同刷新次数的前缀不能混用。- 原地混用当前长度和上一长度，会在一次转移中重复追加元素。
- 先用 32 位做乘法再取模，无法恢复已经溢出的正确计数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 920. 播放列表的数量 | 困难 | 同样把加入一项分成产生新状态与复用旧状态两类，本题关注是否刷新最大值，原题关注是否首次播放新歌。 |
| 629. K 个逆序对数组 | 困难 | 同样按长度与累计指标计数，转移中的一段前驱求和可用前缀和加速。 |