Leetcode 629: K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

Example 1:

Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Constraints:

• 1 <= n <= 1000
• 0 <= k <= 1000

Problem Analysis:

This is a typical problem of using dynamic programming. Suppose function F(n, k) means the number of different arrays with n length and k inverse pairs.

So F(n, 0) = 1.

And T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-1,k-2) + … + T(n-1, k-n+1). As we suggest an array of n-1 length, then we add a number t to form an array of n length, and t is the largest number of the new array.

For better understand the equation, we can assume original array is n-1 length, and we add a new number t to form an array of n length, and t is the biggest number of the new array.

To make new array has k inverse pairs, for the original arrays that in T(n-1, k), we can add t in the last position, for arrays in T(n-1, k-1), we can add t in the n-1 th position, so k-1+1 = k inverse pairs, …, for arrays in T(n-1, k-n+1), we can add t to the first position, so k-n+1+n-1 = k inverse pairs. So we get T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-1, k-2) + … + T(n-1, k-n+1).

And we can also get T(n, k-1) = T(n-1, k-1) + T(n-1, k-2) + … + T(n-1, k-n+2). So T(n, k)-T(n, k-1) = T(n-1, k)-T(n-1, k-n+2)

Solution

class Solution {
public:
    int kInversePairs(int n, int k) {
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = 1;
            if (i + 1 <= n) dp[i + 1][0] = 1;
            for (int j = 1; j <= min(k, i * (i - 1) / 2); ++j) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
                if (j >= i) dp[i][j] = (1000000007 + dp[i][j] - dp[i - 1][j - i]) % 1000000007;
            }
        }

        return dp[n][k];
    }
};

time complexity is O(n*k)

Space complexity is O(n*k)