1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int kInversePairs(int n, int k) {
int[][] dp = new int[n + 1][k + 1], sum = new int[n + 1][k + 1];
dp[1][0] = 1;
Arrays.fill(sum[1], 1);
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
dp[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 ? (sum[i][j - 1] + dp[i][j]) % MOD : dp[i][j];
}
}
return dp[n][k];
}
}
|
wechat
