# Python, Straightforward with Explanation

• Let's try for a top-down dp. Suppose we know `dp[n][k]`, the number of permutations of (1...n) with k inverse pairs.

Looking at a potential recursion for `dp[n+1][k]`, depending on where we put the element (n+1) in our permutation, we may add 0, 1, 2, ..., n new inverse pairs. For example, if we have some permutation of 1...4, then:

• 5 x x x x creates 4 new inverse pairs
• x 5 x x x creates 3 new inverse pairs
• ...
• x x x x 5 creates 0 new inverse pairs

where in the above I'm representing any permutation of 1...4 with x's.
Thus, `dp[n+1][k] = sum_{x=0..n} dp[n][k-x]`.

This dp has `NK` states with `K/2` work, which isn't fast enough. We need to optimize further.

Let `ds[n][k] = sum_{x=0..k-1} dp[n][x]`.
Then `dp[n+1][k] = ds[n][k+1] - ds[n][k-n]`,
and the left hand side is `ds[n+1][k+1] - ds[n+1][k]`.
Thus, we can perform all calculations in terms of `ds`.

Finally, to save space, we will only store the two most recent rows of `ds`, using `ds` and `new`.

In the code, we refer to `-ds[n][k-n+1]` instead of `-ds[n][k-n]` because the `n` being considered is actually n+1. For example, when `n=2`, we are appending information about `ds[2][k]` to `new`, so our formula of `dp[n+1][k] = ds[n][k+1] - ds[n][k-n]` is `dp[2][k] = ds[1][k+1] - ds[1][k-1]`.

``````def kInversePairs(self, N, K):
MOD = 10**9 + 7
ds = [0] + [1] * (K + 1)
for n in xrange(2, N+1):
new = [0]
for k in xrange(K+1):
v = ds[k+1]
v -= ds[k-n+1] if k >= n else 0
new.append( (new[-1] + v) % MOD )
ds = new
return (ds[K+1] - ds[K]) % MOD
``````

• Haha, all of your posts have the same title..

• This post is deleted!

• @awice Beautiful solution! I'm having trouble working out the line `dp[n+1][k] = ds[n][k+1] - ds[n][k-n+1]`.

We have:
`dp[n+1][k]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][k-n]`
`ds[n][k+1]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+...+dp[n][0]`
`ds[n][k-n+1]=dp[n][k-n]+dp[n][k-n-1]+dp[n][k-n-2]+...+dp[n][0]`

Doesn't that mean:
`dp[n+1][k] = ds[n][k+1] - ds[n][k-n+1] + dp[n][k-n]`? Since the `dp[n][k-n]` terms is subtracted out by `ds[n][k-n+1]` and we need to put it back?

• @baselRus I edited my post to fix it and clarify the difference, thanks for pointing it out.

• @awice That makes sense, thank you.

C++ version of the algo below.

Thanks @yangyx for the tip about `+MOD` in the final line of the solution. Not sure why it's not necessary for Python?

``````int kInversePairs(int N, int K) {
long MOD=pow(10,9)+7;
vector<long> ds(vector<long>(K+2,1));
ds[0]=0;
for (int n=2; n<N+1; n++) {
vector<long> dsnew(K+2,0);
for (int k=0; k<K+1; k++) {
dsnew[k+1]=(ds[k+1]-(k>=n ? ds[k-n+1] : 0)+dsnew[k])%MOD;
}
ds=dsnew;
}
return (int)(ds[K+1]-ds[K]+MOD)%MOD;
}
``````

• @baselRus In Python, `x % y` (when `y > 0`) is guaranteed to be non-negative.

• C++ version:

``````class Solution {
public:
int kInversePairs(int n, int k) {
auto c = std::vector<std::vector<unsigned long long>>(n + 1, std::vector<unsigned long long>(k + 1, 0));
auto mod = (int)std::pow(10, 9) + 7;
// base case
for (int j = 0; j <= k; j++) {
c[1][j] = 0;
}
c[1][0] = 1;
// recursion
for (int i = 2; i <= n; i++)
for (int j = 0; j <= k; j++) {
c[i][j] = ((j - 1 < 0 ? 0 : c[i][j - 1]) +
c[i - 1][j] - (j - i < 0 ? 0 : c[i - 1][j - i]) + mod) % mod;
}
return (int)c[n][k];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.