629. K Inverse Pairs Array

Problem

Tags: Dynamic Programming

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 10^9 + 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

Code

JS

// 629. K Inverse Pairs Array (7/2/53435)
// Runtime: 96 ms (85.71%) Memory: 53.04 MB (85.71%) 

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function(n, k) {
    // dp[x][y] 代表在長 x 時有 y 個 inverse pair 的陣列有多少個
    let dp = Array.from(new Array(n+1), () => new Array(k+1).fill(0));
    
    // 如果都沒有 inverse pair 就只有可能是嚴格遞增的那種
    for(let i = 0; i <= n; i++) dp[i][0] = 1;
    
    for(let i = 1; i <= n; i++) {
        for(let j = 1; j <= k; j++) {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % (1e9 + 7);
            if(j >= i) dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + (1e9 + 7)) % (1e9 + 7);
        }
    }
    
    return dp[n][k];
};