class Solution {
public:
int kInversePairs(int n, int k) {
}
};
629. K个逆序对数组
给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。
逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。
由于答案可能很大，只需要返回 答案 mod 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 个逆序对。
说明:
n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。原站题解
javascript 解法, 执行用时: 88 ms, 内存消耗: 41.8 MB, 提交时间: 2023-09-21 15:13:19
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var kInversePairs = function(n, k) {
const MOD = 1000000007;
const f = new Array(2).fill(0).map(() => new Array(k + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j <= k; ++j) {
const cur = i & 1, prev = cur ^ 1;
f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j];
if (f[cur][j] >= MOD) {
f[cur][j] -= MOD;
} else if (f[cur][j] < 0) {
f[cur][j] += MOD;
}
}
}
return f[n & 1][k];
};
golang 解法, 执行用时: 12 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-21 15:13:09
func kInversePairs(n, k int) int {
const mod int = 1e9 + 7
f := [2][]int{make([]int, k+1), make([]int, k+1)}
f[0][0] = 1
for i := 1; i <= n; i++ {
for j := 0; j <= k; j++ {
cur := i & 1
prev := cur ^ 1
f[cur][j] = 0
if j > 0 {
f[cur][j] = f[cur][j-1]
}
if j >= i {
f[cur][j] -= f[prev][j-i]
}
f[cur][j] += f[prev][j]
if f[cur][j] >= mod {
f[cur][j] -= mod
} else if f[cur][j] < 0 {
f[cur][j] += mod
}
}
}
return f[n&1][k]
}
python3 解法, 执行用时: 904 ms, 内存消耗: 171.7 MB, 提交时间: 2023-09-21 15:12:47
MOD = int(1e9) + 7
class Solution:
@staticmethod
@lru_cache(None)
def kInversePairs(n: int, k: int) -> int:
return (Solution.kInversePairs(n, k-1) + Solution.kInversePairs(n-1, k) - \
(Solution.kInversePairs(n-1, k-n) if k >= n else 0)) % MOD if n > 1 and k else int(n > k)
# dp
def kInversePairs2(self, n: int, k: int) -> int:
# dp[n][k] - dp[n][k-1] = dp[n-1][k] - dp[n-1][k-n] if k >= n else dp[n-1][k]
dp = [1] + [0] * k
for i in range(2, n + 1):
next_dp = [1] + [0] * k
for j in range(1, k + 1):
next_dp[j] = (next_dp[j-1] + dp[j] - (dp[j-i] if j >= i else 0)) % MOD
dp = next_dp
return dp[-1]
# dp 2
def kInversePairs3(self, n: int, k: int) -> int:
f = [1] + [0] * k
for i in range(1, n + 1):
g = [0] * (k + 1)
for j in range(k + 1):
g[j] = (g[j - 1] if j - 1 >= 0 else 0) - (f[j - i] if j - i >= 0 else 0) + f[j]
g[j] %= MOD
f = g
return f[k]
java 解法, 执行用时: 18 ms, 内存消耗: 42.1 MB, 提交时间: 2023-09-21 15:11:13
class Solution {
private static final int MOD = 1000000007;
// dp 1
public int kInversePairs(int n, int k) {
// dp[n][k] - dp[n][k-1] = dp[n-1][k] - dp[n-1][k-n] if k >= n else dp[n-1][k]
int[] dp = new int[k + 1];
Arrays.fill(dp, 0);
dp[0] = 1;
for(int i=2;i<=n;i++){
int[] next_dp = new int[k + 1];
Arrays.fill(next_dp, 0);
next_dp[0] = 1;
for(int j=1;j<=k;j++){
next_dp[j] = (next_dp[j-1] + dp[j]) % MOD;
if(j >= i){
next_dp[j] = (next_dp[j] - dp[j-i] + MOD) % MOD;
}
}
dp = next_dp;
}
return dp[k];
}
// dp 2
public int kInversePairs2(int n, int k) {
int[][] f = new int[2][k + 1];
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
int cur = i & 1, prev = cur ^ 1;
f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j];
if (f[cur][j] >= MOD) {
f[cur][j] -= MOD;
} else if (f[cur][j] < 0) {
f[cur][j] += MOD;
}
}
}
return f[n & 1][k];
}
}
cpp 解法, 执行用时: 56 ms, 内存消耗: 6.5 MB, 提交时间: 2023-09-21 15:09:56
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int kInversePairs(int n, int k) {
vector<vector<int>> f(2, vector<int>(k + 1));
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
int cur = i & 1, prev = cur ^ 1;
f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j];
if (f[cur][j] >= mod) {
f[cur][j] -= mod;
}
else if (f[cur][j] < 0) {
f[cur][j] += mod;
}
}
}
return f[n & 1][k];
}
};