# Share my O(n*k) time, O(k) space solution in C++

• `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];
}
};
``````

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