`f[i][j]`

means the number of different arrays with length `i`

that have `k`

inverse pairs.

To find out f[n][k], say we move and fix the largest number `n`

one position forward, then we have at least one inverse pair now => # is `f[n-1][k-1]`

.

We could also move it `2`

position forward, then we have at least two inverse pairs now => # is `f[n-1][k-2]`

.

`...`

`f[n][k] = f[n-1][k] + f[n-1][k-1] + ... + f[n-1][0]`

One problem is that the most left position we can move the largest number is the first position, where we will have at least `n-1`

inverse pairs. So the formula should be:

`f[n][k] = f[n-1][k] + f[n-1][k-1] + ... + f[n-1][max(0, k-n+1)]`

```
class Solution {
public:
int kInversePairs(int n, int k) {
// how to solve using DP?
// by change the position of the largest number (the last number 'n')
// it's not hard to see: f[n][k] = f[n-1][k] + f[n-1][k-1] + ... + f[n-1][0]
// since we only need the f[n-1][:], we don't need to store everything
// f[0] = 1, since there is only one number at the beginning
vector<int> f(k+1, 0);
f[0] = 1;
int MOD = 1000000007;
for (int i=2; i<=n; i++) {
// given i distinct numbers, there can be at most i*(i-1)/2 inverse pairs, so we don't need to update everything
int index = min(i*(i-1)/2, k);
for (int j=1; j<=index; j++)
f[j] = (f[j] + f[j-1]) % MOD;
// fix the problem of max(0, j-i+1)
for (int j=index; j>i-1; j--)
f[j] = ((f[j]-f[j-i])%MOD + MOD) % MOD;
}
return f[k];
}
};
```