这题递推式很好推，但是同样很多细节写起来还有点吃力。从递推式开始说，这题有两种思路，一种是官方题解里说的考虑任意序列中第n个元素是序列中第k大的数，这样就有从中可以找出与组成逆序对的n-k个数，而加上中原本的逆序对就组成了这个任意序列中的所有逆序对，于是我们有
其中k为第k大的数，这样从和错位相减得到最终的递推式：
第二种思路同样是考虑，考虑将其插入由组成的序列中，假设插入的位置为k，由于大于前面序列中的所有数所以将会构成n-k个逆序对，序列中的逆序对总数为，n-k加上组成的序列中原来包含的逆序对个数，同样可以得到类似上面递推的结果，但是这种思路可以引导出另外一种解法——前缀和。
第一种的实现应该无需赘述，唯一值的注意的是在官方的解法中，通过一个小技巧实现了滚动数组，通过令
int cur = i&1
int prev = cur^1就可以简单的让两个数组实现滚动，其他的部分就是根据上述的到的递推式递推即可
const int MOD = 1e9+7;
const int maxn = 1004;
class Solution {
public:
int kInversePairs(int n, int k) {
vector<vector<int>> dp(2,vector<int>(MAXN));
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i ++){
int cur = i&1 , prev = 1^cur;
for(int j = 0 ; j <= k ; j ++){
dp[cur][j] = ((j>=1?dp[cur][j-1]:0)-(j>=i?dp[prev][j-i]:0)+MOD)%MOD;
dp[cur][j] = (dp[cur][j]+dp[prev][j])%MOD;
}
}
return dp[n&1][k];
}
};第二种解法，考虑当j≥i和j<i这两种情况需要不同的处理方法，当j<i时，因为j<i所以插入的位置只能到i-j为止，而当j≥i时，不会出现数值i插入的位置过于靠前导致逆序对的数量超过j的现象所以可以插入到长度为i的序列任意位置，所以，很容易看出来这相当于两个dp数组前缀和的差，我们只需要在每一次dp运算后更新sum数组即可。
int kInversePairs(int n, int k) {
int dp[maxn];
int sum[maxn];
memset(sum,0,sizeof(sum));
// sum[1] = 1;
for(int i = 1 ; i <= n ; i ++){
dp[1] = 1;
for(int j = 2;j<=k+1;j++){
dp[j]= (sum[j]-sum[max(j-i,0)]+MOD)%MOD;
// 1 = sum1 - sum 0
}
for(int j = 1 ; j <= k+1 ; j ++){
sum[j] = (sum[j-1]+dp[j])%MOD;
}
}
return dp[k+1];
}