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


  • 0
    M

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

Log in to reply
 

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