O(n*K) C++ [Bottom Up from 0 inversions to K]


  • 0
    D

    int64_t dp[1005][1005];
    int64_t mod = 1000000007;
    class Solution {
    public:
    int kInversePairs(int n, int k) {

        for(int i=0;i<=k;i++){
            for(int j=0;j<=n;j++){
               dp[i][j] = 0;
               if(i == 0){
                   dp[i][j] = 1;
               }
               
            }
        }
        dp[0][0] = 0;
        for(int i=1;i<=k;i++){
            for(int j=1;j<=n;j++){
                int64_t x = 0;
                if(i-j >= 0){
                    x = dp[i-j][j-1];
                }
                dp[i][j] = ((dp[i-1][j]%mod + dp[i][j-1]%mod)%mod - x + mod)%mod;
               
            }
        }
        int64_t y = 0;
        if(k>0){
            y = dp[k-1][n];
        }
        return (dp[k][n]-y+mod)%mod;
    }
    

    };


Log in to reply
 

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