# Leetcode 629 - K inverse pairs array

Note:

• Based on the range of k an n, it’s easy to tell that BFS/DFS will TLE.
• For questions like the number of combinations, it’s usually DP.
• dp[i][j] means how many combinations to get j paris using [1, i].
• Thoughts:
• Take dp[4][2] for example,
• We can learn the pattern DP[4][2] = DP[3][2] + DP[3][1] + DP[3][0].
• The deduction is:
• How do we get the bound [0, i-1] ?
• Explaination: When we insert n into the end of [0, n-1], there is no more new pairs. When we insert n into the start of [0, n-1]. We generated another n - 1 pairs with [0, n-1].
• We can get the dp deduction by:
• Initialize dp as dp[i][0] === 1.
• Details:
• Need to check if j >= i, otherwise dp[i-1][j-i] doesn’t make sense.
• dp[i][j] might be negative. so if it it, to get the mod of a negative number, we have to add MOD to it first.

Question:

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:

Code: