友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
629. K 个逆序对数组
对于一个整数数组 nums，逆序对是一对满足 0 <= i < j < nums.length 且 nums[i] > nums[j] 的整数对 [i, j]。
给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大，只需要返回对 109 + 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 个逆序对。
提示：
-
1 <= n <= 1000 -
0 <= k <= 1000
思路分析
有点懵逼，似懂非懂。
从暴力破解，再加备忘录，最后到动态规划，这样的思路比较容易理解。
-
一刷(暴力破解)
-
一刷(备忘录)
-
一刷(动态规划)
-
一刷(动态规划)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-09 19:55:53
*/
public int kInversePairs(int n, int k) {
return dfs(n, k);
}
private int dfs(int n, int k) {
if (k > n * (n - 1) / 2) {
return 0;
}
if (n == 1) {
return k == 0 ? 1 : 0;
}
int MOD = 1_000_000_007;
int result = 0;
for (int i = Math.max(0, k - n + 1); i <= k; i++) {
result += dfs(n - 1, i) % MOD;
result %= MOD;
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-09 20:22:16
*/
public int kInversePairs(int n, int k) {
int[][] memo = new int[n + 1][k + 1];
for (int[] m : memo) {
Arrays.fill(m, -1);
}
return dfs(n, k, memo);
}
private int dfs(int n, int k, int[][] memo) {
if (k > n * (n - 1) / 2) {
return 0;
}
if (n == 1) {
return k == 0 ? 1 : 0;
}
if (memo[n][k] != -1) {
return memo[n][k];
}
int MOD = 1_000_000_007;
int result = 0;
for (int i = Math.max(0, k - n + 1); i <= k; i++) {
result += dfs(n - 1, i, memo) % MOD;
result %= MOD;
}
return memo[n][k] = result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-09 20:25:24
*/
public int kInversePairs(int n, int k) {
int[][] dp = new int[n + 1][k + 1];
dp[1][0] = 1;
int MOD = 1_000_000_007;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= Math.min(k, i * (i - 1) / 2); j++) {
for (int l = Math.max(0, j - i + 1); l <= j; l++) {
dp[i][j] = (dp[i][j] + dp[i - 1][l]) % MOD;
}
}
}
return dp[n][k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-09 20:35:42
*/
public int kInversePairs(int n, int k) {
// dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i-1]
// dp[i][j-1] = dp[i-1][j-1] + ... + dp[i-1][j-1-(i-1-1)] + dp[i-1][j-1-i-1]
// dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1-i-1]
long[][] dp = new long[n + 1][k + 1];
dp[1][0] = 1;
int MOD = 1_000_000_007;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= Math.min(k, i * (i - 1) / 2); j++) {
// dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-i]
// 奇怪：为啥这里要加 MOD ？
dp[i][j] = (dp[i - 1][j] + (j >= 1 ? dp[i][j - 1] : 0)
- (j >= i ? dp[i - 1][j - i] : 0) + MOD) % MOD;
}
}
return (int) dp[n][k];
}