Java O(nk) Time O(k) Space DP Solution


  • 1
    public static int kInversePairs(int n, int k) {   
      int[] dp = new int[k+1];
      dp[0] = 1; int mod = 1000000007;
      for (int i=1;i<=n;i++) {
          int[] temp = new int[k+1];
          for (int j=0;j<=k;j++) {
              if (j==0) temp[j] = 1;
              else {
                temp[j] = temp[j-1] + dp[j]; 
                temp[j] %= mod;
                if (j >= 1 + Math.min(i-1, j))  temp[j] += mod - dp[j-1-Math.min(i-1, j)];
                temp[j] %= mod;
              }
          }
          dp = temp;
      }
      return dp[k];
    }
    

  • 0
    S

    how come you had : 1 + Math.min(i-1, j)

    if (j >= 1 + Math.min(i-1, j))  temp[j] += mod - dp[j-1-Math.min(i-1, j)];
    

    I think j >= i is enough , because if j >=i then j > i-1 , then Math.min(i-1, j) = i-1, so your condition reduce to j >= i.

    here is my AC:

    public int kInversePairs(int n, int k) {
            int[][] inverse = new int[2][k+1];
            inverse[0][0] = 1;
            int mod = 1000000007;
            /**
             * inverse[n+1][k] = inverse[n][k] + inverse[n][k-1] + ... + inverse[n][k-n]
             * inverse[n+1][k-1] =               inverse[n][k-1] + ... + inverse[n][k-n] + inverse[n][k-n-1]
             *
             * so inverse[n+1][k] = inverse[n+1][k-1] + inverse[n][k] - inverse[n][k-n-1];
             *
             * so inversen[n][k] = inverse[n][k-1] + inverse[n-1][k] + inverse[n-1][k-n];
             *
             **/
    
            for (int i = 1; i <= n; i++) {
                inverse[1][0] = 1;
                for (int j = 1; j <= k; j++) {
                    inverse[1][j] = inverse[1][j-1] + inverse[0][j];
                    inverse[1][j] %= mod;
                    if (j >= i) {
                        inverse[1][j] += mod - inverse[0][j-i];
                        inverse[1][j] %= mod;
                    }
                }
                int[] tmp = inverse[0];
                inverse[0] = inverse[1];
                inverse[1] = tmp;
            }
            return inverse[0][k];
        }
    

Log in to reply
 

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