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

---

解法1

这道题的难点其实是在于, 怎么计算而不是一个一个去数可能性.

我们以 n = 4 为例. [1,2,3,4] ,当我们把 4 往左移动 2 个位置, 数组变成了 [1,4,2,3] , 这时数对是由两个.因为在 4 的右边有两个比它小的数.

这个道理对于移动 y 个位置依然成立.

在计算了 n = 4 的所有情况之后, 我们把数字 5 添加到最右边, 然后来尝试计算 n = 5 时的情况.

[1,4,2,3,5] , 当把 5 向左移动 3 个位置 , [1,5,4,2,3] 数对就有了 3 + 2 = 5个, 4 的移动位置加上 5 的移动位置.

得到一般计算式, f(n , k) = f(n - 1, k) + f(n - 1, k - 1) + f(n - 1, k - 2) + ... + f(n - 1, k - n)

当 k - n < 0 时, 计算到f(n - 1, 0)

public class Solution {
    public int kInversePairs(int n, int k) {

        // 前一次的结算结果
        long[] pre = new long[k + 1];

        for (int i = 1; i <= n; i++) {

            // 本次的计算结果
            long[] cur = new long[k + 1];
            // k = 1时, 结果为1
            cur[0] = 1;
            for (int j = 1; j <= k; j++) {
                for (int p = 0, limit = Math.min(j, i - 1); p <= limit; p++)
                    cur[j] += pre[j - p];
                cur[j] %= 1000000007;
            }
            
            pre = cur;
        }
        return (int)pre[k];
    }
}