629-K个逆序对数组(K Inverse Pairs Array)

原文链接: https://leetcode-cn.com/problems/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⁹ + 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

中文题目

给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回答案 mod 10⁹ + 7 的值。

示例 1:

输入: n = 3, k = 0
输出: 1
解释: 
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2:

输入: n = 3, k = 1
输出: 2
解释: 
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

说明:

n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

通过代码

高赞题解

序列 DP

从 $n$ 和 $k$ 数据范围均为 $10^3$ 可以看出这是一道二维的动态规划题。

定义 $f[i][j]$ 为考虑使用数值 $[1,i]$，凑成逆序对数量恰好为 $j$ 的数组个数。

不失一般性的考虑 $f[i][j]$ 该如何计算，对第 $i$ 个数（即数值为 $i$ 的数）所在位置进行讨论，共有 $i$ 种选择。

假设第 $i$ 个数所在位置为 $k$，由于数值 $i$ 为整个数组的最大值，因此数值 $i$ 与前面所有数均不形成逆序对，与后面的所有数均形成逆序对。因此与数值 $i$ 直接相关的逆向对的数量为 $(i - 1)- k$，由此也得出与 $i$ 不相关的逆序对数量为 $j - (i - 1 - k)$，而与 $i$ 不相关的逆序对数量由 $f[i - 1][x]$ 可得出。

举个 🌰 帮助大家理解：

当数值 $i$ 放置在下标为 $0$ 的位置上，那么由数值 $i$ 产生的逆序对数量为 $i - 1$，总的逆序对数量为 $j$，因此由数值范围为 $[1, i - 1]$（与数值 $i$ 不相关）构成的逆序对数量为 $j - (i - 1)$，即 $f[i - 1][j - (i - 1)]$；
当数值 $i$ 放置在下标为 $1$ 的位置上，那么由数值 $i$ 产生的逆序对数量为 $(i - 1) - 1$，总的逆序对数量为 $j$，因此由数值范围为 $[1, i - 1]$（与数值 $i$ 不相关）构成的逆序对数量为 $j - (i - 1 - 1)$，即 $f[i - 1][j - (i - 1 - 1)]$；

…
当数值 $i$ 放置在下标为 $k$ 的位置上，那么由数值 $i$ 产生的逆序对数量为 $(i - 1) - k$，总的逆序对数量为 $j$，因此由数值范围为 $[1, i - 1]$（与数值 $i$ 不相关）构成的逆序对数量为 $j - (i - 1 - k)$，即 $f[i - 1][j - (i - 1 - k)]$。

综上，最终 $f[i][j]$ 转移方程为（$k$ 为数值 $i$ 放置的位置）：

$$
f[i][j] = \sum_{k = 0}^{i - 1}(f[i - 1][j - (i - 1 - k)])
$$

共有 $n * k$ 个状态，每个 $f[i][j]$ 的计算需要枚举数值 $i$ 所在位置并进行累加，总的复杂度为 $O(n^2 *k)$，计算量为 $10^9$，会 TLE。

状态数量不可减少，考虑如何优化单个状态的转移过程。

不难发现 $\sum_{k = 0}^{i - 1}(f[i - 1][j - (i - 1 - k)])$ 部分为上一次转移结果 $f[i - 1][x]$ 的某个前缀，可以使用前缀和数组进行优化，从而将计算单个状态的复杂度从 $O(n)$ 降到 $O(1)$。

一些细节：为处理负数问题，我们可以在取模之前先加一次 mod；另外需要对 $j$ 和 $i$ 的大小进行分情况讨论，防止数值 $i$ 放置的位置“过于靠前”导致组成逆序对的数量超过 $j$。

代码：

[]
class Solution {
    int mod = (int)1e9+7;
    public int kInversePairs(int n, int k) {
        int[][] f = new int[n + 1][k + 1];
        int[][] sum = new int[n + 1][k + 1];
        f[1][0] = 1;
        Arrays.fill(sum[1], 1);
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = j < i ? sum[i - 1][j] : (sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1] + mod) % mod;
                sum[i][j] = j == 0 ? f[i][j] : (sum[i][j - 1] + f[i][j]) % mod;
            }
        }
        return f[n][k];
    }
}

时间复杂度：$O(n * k)$
空间复杂度：$O(n * k)$

其他「序列 DP」相关内容

考虑加练如下「序列 DP」题目 🍭🍭

题目	题解	难度	推荐指数
354. 俄罗斯套娃信封问题	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
368. 最大整除子集	LeetCode 题解链接	中等	🤩🤩🤩🤩
446. 等差数列划分 II - 子序列	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
583. 两个字符串的删除操作	LeetCode 题解链接	中等	🤩🤩🤩🤩
673. 最长递增子序列的个数	LeetCode 题解链接	中等	🤩🤩🤩🤩
740. 删除并获得点数	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
978. 最长湍流子数组	LeetCode 题解链接	中等	🤩🤩🤩
1035. 不相交的线	LeetCode 题解链接	中等	🤩🤩🤩🤩
1143. 最长公共子序列	LeetCode 题解链接	中等	🤩🤩🤩🤩
1218. 最长定差子序列	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
1473. 粉刷房子 III	LeetCode 题解链接	困难	🤩🤩🤩🤩
1713. 得到子序列的最少操作次数	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或加入「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
18757	35927	52.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途