C++ O(n * k) with Explanation


  • 0

    The O(n * n * k) solution can be found here

    This post try to help you understand how does O(n * k) come out.
    Let us use dp[n][k] denote the sum of val[n][k] + val[n][k - 1] + ... + val[n][0]

    val[n][k] denote number 1 - n number contain k Inverse Pairs
    dp[n][k] = val[n][0] + val[n][1] + ....... + val[n][k]
    so , we have
    dp[n][k] = dp[n][k - 1] + val[n][k]
    val[n][k] = val[n - 1][k] + val[n - 1][k - 1] + ...... + val[n - 1][k - n + 1]
    val[n][k] = dp[n - 1][k] - dp[n - 1][k - n]
    so we have
    dp[n][k] = dp[n][k - 1] + dp[n - 1][k] - dp[n - 1][k - n];
    

    SO! We get the following code.

    class Solution {
      const int mod = 1000000007;
    public:
      int kInversePairs(int n, int k) {
        if (n == 1)
          return k == 0 ? 1 : 0;
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        for (int i = 0; i <= k; i++)
            dp[1][i] = 1;
        // for n numbers
        for (int i = 2; i <= n; i++) {
          // for k combines
          for (int j = 0; j <= k; j++) {
            dp[i][j] = (j - 1 >= 0 ? dp[i][j - 1] : 0);
            int val = (dp[i - 1][j] - (j - i >= 0 ? dp[i - 1][j - i] : 0) + mod) % mod;
            dp[i][j] = (dp[i][j] + val) % mod;
          }
        }
        return (dp[n][k] - dp[n][k - 1] + mod) % mod;
      }
    };
    

Log in to reply
 

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