# C++ O(n * k) with Explanation

• The O(n * n * k) solution can be found here

This post try to help you understand how does O(n * k) come out.
Let us use `dp[n][k]` denote the `sum` of `val[n][k] + val[n][k - 1] + ... + val[n][0]`

``````val[n][k] denote number 1 - n number contain k Inverse Pairs
dp[n][k] = val[n][0] + val[n][1] + ....... + val[n][k]
so , we have
dp[n][k] = dp[n][k - 1] + val[n][k]
val[n][k] = val[n - 1][k] + val[n - 1][k - 1] + ...... + val[n - 1][k - n + 1]
val[n][k] = dp[n - 1][k] - dp[n - 1][k - n]
so we have
dp[n][k] = dp[n][k - 1] + dp[n - 1][k] - dp[n - 1][k - n];
``````

SO! We get the following code.

``````class Solution {
const int mod = 1000000007;
public:
int kInversePairs(int n, int k) {
if (n == 1)
return k == 0 ? 1 : 0;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
for (int i = 0; i <= k; i++)
dp[1][i] = 1;
// for n numbers
for (int i = 2; i <= n; i++) {
// for k combines
for (int j = 0; j <= k; j++) {
dp[i][j] = (j - 1 >= 0 ? dp[i][j - 1] : 0);
int val = (dp[i - 1][j] - (j - i >= 0 ? dp[i - 1][j - i] : 0) + mod) % mod;
dp[i][j] = (dp[i][j] + val) % mod;
}
}
return (dp[n][k] - dp[n][k - 1] + mod) % mod;
}
};
``````

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