问题描述：
给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。
逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。
由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。
问题分析：
dp[n][k]表示1到n的数字中，逆序对的个数为k的不同数组的个数
如果n放在最后的位置，那么k个逆序对就在前面n-1的数组中
如果n放在倒数第二个位置，那么就会出现一个逆序对，则前面n-1的数组中有k-1个逆序对
…
如果n放在第一个位置，那么就会出现n-1个逆序对，则前面n-1的数组中有k-n+1个逆序对
递推关系：dp[n][k] = dp[n - 1][k] + dp[n - 1][k - 1] + dp[n - 1][k - 2] + … + dp[n - 1][k+1-n+1] + dp[n -1][k - n + 1]
dp[n][k + 1] = dp[n - 1][k + 1] + dp[n - 1][k] + … +dp[n - 1][k + 1 -n + 1]
因此： dp[n][k + 1] = dp[n - 1][k + 1] + dp[n][k] - dp[n - 1][k - n + 1]
由于dp[n][k]可能出现负数，因此dp[n][k] = dp[n][k] + MOD
问题求解：
class Solution {
public int kInversePairs(int n, int k) {
long[][] dp = new long[n + 1][k + 1];
if(k > n*(n - 1) / 2 || k < 0)
return 0;
if(k == 0 || k == n *(n - 1) / 2)
return 1;
int mod = 1000000007;
dp[2][0] = 1;
dp[2][1] = 1;
for(int i = 3 ; i <= n ; i ++){
dp[i][0] = 1;
for(int j = 1 ; j <= Math.min(k, n * (n - 1) / 2); j ++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
if(j >= i)
dp[i][j] -= dp[i - 1][j - i];
dp[i][j] = (dp[i][j] + mod) % mod; //处理dp[i][j]为负数的情况
}
}
return (int)dp[n][k];
}
}
问题总结：
老规矩先可以看一下官方的解析。
我们可以用动态规划的方法来解决本题。
设 f[i][j]f[i][j] 表示我们使用数字 1, 2, \cdots, i1,2,⋯,i 的排列构成长度为 ii 的数组，并且恰好包含 jj 个逆序对的方案数。在进行状态转移时，我们可以考虑第 ii 个元素选取了 1, 2, \cdots, i1,2,⋯,i 中的哪个数字。
假设我们选取了数字 kk，那么数组的前 i-1i−1 个元素由 1, \cdots, k-11,⋯,k−1 以及 k+1, \cdots, ik+1,⋯,i 的某个排列构成。数组中的逆序对的个数可以看成如下的两部分之和：
数字 kk 与前 i-1i−1 个元素产生的逆序对的个数；
前 i-1i−1 个元素「内部」产生的逆序对个数。
对于第一部分而言，我们可以求出：数字 kk 会贡献 i-ki−k 个逆序对，即 k+1, \cdots, ik+1,⋯,i 与 kk 分别产生一个逆序对。
对于第二部分而言，我们希望它能够有 j - (i-k)j−(i−k) 个逆序对，这样才能一共有 jj 个逆序对。由于我们关心的是前 i-1i−1 个元素「内部」产生的逆序对个数，而逆序对只和元素的「相对大小」有关，因此我们可以：
1, \cdots, k-11,⋯,k−1 这些元素保持不变；
k+1, \cdots, ik+1,⋯,i 这些元素均减少 11，变成 k, \cdots, i-1k,⋯,i−1。
使得前 i-1i−1 个元素中，任意两个元素的相对大小都不发生变化。此时，我们的目标变成了「对于 1, 2, \cdots, i-11,2,⋯,i−1，希望它能够有 j-(i-k)j−(i−k) 个逆序对」，这就是动态规划中的子任务 f[i-1][j-(i-k)]f[i−1][j−(i−k)]。
因此，我们就可以通过枚举 kk 得到状态转移方程：
f[i][j] = \sum_{k=1}^i f[i-1][j-(i-k)] = \sum_{k=0}^{i-1} f[i-1][j-k]
f[i][j]=
k=1
∑
i
f[i−1][j−(i−k)]=
k=0
∑
i−1
f[i−1][j−k]
边界条件为：
f[0][0] = 1f[0][0]=1，即不用任何数字可以构成一个空数组，它包含 00 个逆序对；
f[i][j < 0] = 0f[i][j<0]=0，由于逆序对的数量一定是非负整数，因此所有 j < 0j<0 的状态的值都为 00。我们不需要显式地存储这些状态，只需要在进行状态转移遇到这样的项时，注意特殊判断即可。
最终的答案即为 f[n][k]f[n][k]。
优化
上述动态规划的状态数量为 O(nk)O(nk)，而求出每一个 f[i][j]f[i][j] 需要 O(n)O(n) 的时间复杂度，因此总时间复杂度为 O(n^2k)O(n
2
k)，会超出时间限制，我们必须要进行优化。
我们考虑 f[i][j-1]f[i][j−1] 和 f[i][j]f[i][j] 的状态转移方程：
\left{ \begin{aligned} & f[i][j-1] && = && \sum_{k=0}^{i-1} f[i-1][j-1-k] \ & f[i][j] && = && \sum_{k=0}^{i-1} f[i-1][j-k] \end{aligned} \right.
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎧
f[i][j−1]
f[i][j]
=
k=0
∑
i−1
f[i−1][j−1−k]
k=0
∑
i−1
f[i−1][j−k]
可以得到从 f[i][j-1]f[i][j−1] 到 f[i][j]f[i][j] 的递推式：
f[i][j] = f[i][j-1] - f[i-1][j-i] + f[i-1][j]
f[i][j]=f[i][j−1]−f[i−1][j−i]+f[i−1][j]
这样我们就可以在 O(1)O(1) 的时间计算出每个 f[i][j]f[i][j]，总时间复杂度降低为 O(nk)O(nk)。
此外，由于 f[i][j]f[i][j] 只会从第 f[i-1][…]f[i−1][…] 和 f[i][…]f[i][…] 转移而来，因此我们可以对动态规划使用的空间进行优化，即使用两个一维数组交替地进行状态转移，空间复杂度从 O(nk)O(nk) 降低为 O(k)O(k)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/k-inverse-pairs-array/solution/kge-ni-xu-dui-shu-zu-by-leetcode-solutio-0hkr/
来源：力扣（LeetCode）