共计 2514 个字符，预计需要花费 7 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 629. K 个逆序对数组 ，难度为 艰难。
Tag :「序列 DP」、「前缀和」
给出两个整数 n 和 k，找出所有蕴含从 1 到 n 的数字，且恰好领有 k 个逆序对的不同的数组的个数。
逆序对的定义如下：对于数组的第 i 个和第 j 个元素，如果满 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
因为答案可能很大，只须要返回 答案 mod $10^9 + 7$ 的值。
示例 1:
输出: n = 3, k = 0
输入: 1
解释:
只有数组 [1,2,3] 蕴含了从 1 到 3 的整数并且正好领有 0 个逆序对。示例 2:
输出: n = 3, k = 1
输入: 2
解释:
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。阐明:
-
n的范畴是[1, 1000]并且k的范畴是[0, 1000]。
序列 DP
从 $n$ 和 $k$ 数据范畴均为 $10^3$ 能够看出这是一道二维的动静布局题。
定义 $f[i][j]$ 为思考应用数值 $[1,i]$，凑成逆序对数量恰好为 $j$ 的数组个数。
不失一般性的思考 $f[i][j]$ 该如何计算，对第 $i$ 个数（即数值为 $i$ 的数）所在位置进行探讨，共有 $i$ 种抉择。
假如第 $i$ 个数所在位置为 $k$，因为数值 $i$ 为整个数组的最大值，因而数值 $i$ 与后面所有数均不造成逆序对，与前面的所有数均造成逆序对。因而与数值 $i$ 间接相干的逆向对的数量为 $(i – 1)- k$，由此也得出与 $i$ 不相干的逆序对数量为 $j – (i – 1 – k)$，而与 $i$ 不相干的逆序对数量由 $f[i – 1][x]$ 可得出。
举个 🌰 帮忙大家了解：
- 当数值 $i$ 搁置在下标为 $0$ 的地位上，那么由数值 $i$ 产生的逆序对数量为 $i – 1$，总的逆序对数量为 $j$，因而由数值范畴为 $[1, i – 1]$（与数值 $i$ 不相干）形成的逆序对数量为 $j – (i – 1)$，即 $f[i – 1][j – (i – 1)]$；
-
当数值 $i$ 搁置在下标为 $1$ 的地位上，那么由数值 $i$ 产生的逆序对数量为 $(i – 1) – 1$，总的逆序对数量为 $j$，因而由数值范畴为 $[1, i – 1]$（与数值 $i$ 不相干）形成的逆序对数量为 $j – (i – 1 – 1)$，即 $f[i – 1][j – (i – 1 – 1)]$；
…
- 当数值 $i$ 搁置在下标为 $k$ 的地位上，那么由数值 $i$ 产生的逆序对数量为 $(i – 1) – k$，总的逆序对数量为 $j$，因而由数值范畴为 $[1, i – 1]$（与数值 $i$ 不相干）形成的逆序对数量为 $j – (i – 1 – k)$，即 $f[i – 1][j – (i – 1 – k)]$。
综上，最终 $f[i][j]$ 转移方程为（$k$ 为数值 $i$ 搁置的地位）：
$$
f[i][j] = \sum_{k = 0}^{i – 1}(f[i – 1][j – (i – 1 – k)])
$$
共有 $n * k$ 个状态，每个 $f[i][j]$ 的计算须要枚举数值 $i$ 所在位置并进行累加，总的复杂度为 $O(n^2 *k)$，计算量为 $10^9$，会 TLE。
状态数量不可缩小，思考如何优化单个状态的转移过程。
不难发现 $\sum_{k = 0}^{i – 1}(f[i – 1][j – (i – 1 – k)])$ 局部为上一次转移后果 $f[i – 1][x]$ 的某个前缀，能够应用前缀和数组进行优化，从而将计算单个状态的复杂度从 $O(n)$ 降到 $O(1)$。
一些细节：为解决正数问题，咱们能够在取模之前先加一次 mod；另外须要对 $j$ 和 $i$ 的大小进行分状况探讨，避免数值 $i$ 搁置的地位“过于靠前”导致组成逆序对的数量超过 $j$。
代码（$P1$ $P2$ 别离为应用 long 和不应用 long）：
class Solution {int mod = (int)1e9+7;
public int kInversePairs(int n, int k) {long[][] f = new long[n + 1][k + 1];
long[][] sum = new long[n + 1][k + 1];
f[1][0] = 1;
Arrays.fill(sum[1], 1);
for (int i = 2; i <= n; i++) {for (int j = 0; j <= k; j++) {f[i][j] = j < i ? sum[i - 1][j] : sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1];
f[i][j] = (f[i][j] + mod) % mod;
sum[i][j] = j == 0 ? f[i][j] : sum[i][j - 1] + f[i][j];
sum[i][j] = (sum[i][j] + mod) % mod;
}
}
return (int)f[n][k];
}
}class Solution {int mod = (int)1e9+7;
public int kInversePairs(int n, int k) {int[][] f = new int[n + 1][k + 1];
int[][] sum = new int[n + 1][k + 1];
f[1][0] = 1;
Arrays.fill(sum[1], 1);
for (int i = 2; i <= n; i++) {for (int j = 0; j <= k; j++) {f[i][j] = j < i ? sum[i - 1][j] : (sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1] + mod) % mod;
sum[i][j] = j == 0 ? f[i][j] : (sum[i][j - 1] + f[i][j]) % mod;
}
}
return f[n][k];
}
}- 工夫复杂度：$O(n \times k)$
- 空间复杂度：$O(n \times k)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.629 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
