629. K Inverse Pairs Array

Description

image-20210904111922280

Solution

The tricky point is how to get the recurrence relation. We could ituitively give dp[i][j] as for i length array, the number of k’s inverse pairs. Then let’s figure out the recurrence relation

Assume we already have dp[n][k], then we add one item afterwards. We have

1
2
[1 2 3 4 5] 6
↑ ↑ ↑ ↑ ↑ ↑

We can insert 6 into 6 slot to get more 5,4,3,2,1,0 more inverse pairs.

so dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... + dp[n-1][k - (n-1)]

Then we could use dp[n][k-1] = dp[n-1]][k-1] + dp[n-1][k-2] + ... + dp[n-1][k-1 - (n-1)] to replace some terms in previous formula.

dp[n][k] = dp[n-1][k] + dp[n][k-1] - dp[n-1][k-n]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    const int MOD = 1E9 + 7;
public:
    int kInversePairs(int n, int k) {
        vector<vector<int>> dp(n+1, vector<int>(k+1));
        //dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + dp[n-1][k-2] ... + dp[n-1][k-(n-1)]
        //dp[n][k-1] = dp[n-1][k-1] + dp[n-1][k-2] + ... + dp[n-1][k-1 - (n-1)]
        //dp[n][k] = dp[n][k-1] + dp[n-1][k] - dp[n-1][k-n]
        dp[1][0] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j <= k && j <= (i-1)*i/2; j++){
                if(j == 0){
                    dp[i][j] = 1;
                    continue;
                }
                int val = (dp[i-1][j] - (j >= i ? dp[i-1][j-i] : 0) + MOD) % MOD;
                dp[i][j] = (dp[i][j-1] + val) % MOD;
            }
        }
        return dp[n][k];
    }
};

image-20210904131030621