C++ Clean & Clear O(k) Space, O(nk) Time DP Solution


  • 0
    F
    class Solution {
        long long base = 1000000007;
    public:
        int kInversePairs(int n, int k) {
            vector<int> dp0 (k + 1), dp1(k + 1);
            dp0[0] = dp1[0] = 1;
            for (int i = 1; i <= n; ++ i)
            {
                for (int j = 1; j <= k; ++ j)
                    dp1[j] = (dp1[j - 1] + dp0[j] + base - (j - i >= 0 ? dp0[j - i] : 0)) % base; 
                swap(dp0, dp1); //swap costs O(1) in C++
            }
            return dp0.back();
        }
    };
    

Log in to reply
 

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