# 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]`

.

- Explaination: When we insert
- We can get the dp deduction by:

- Take
- 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.

- Need to check if

`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:`

1 | Input: n = 3, k = 1 |

`Code:`

1 | /** |