629.K个逆序对数组

dp, https://leetcode.cn/problems/k-inverse-pairs-array/description/

对于一个整数数组 nums，逆序对是一对满足 0 <= i < j < nums.length 且 nums[i] > nums[j]的整数对 [i, j] 。

给你两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个 逆序对 的不同的数组的个数。由于答案可能很大，只需要返回对 109 + 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 个逆序对。

提示：

1 <= n <= 1000
0 <= k <= 1000

通过动态规划来解决。需要计算包含从 1 到 n 的数字且恰好拥有 k 个逆序对的不同数组的个数。由于答案可能非常大，需要对 10^9 + 7 取模。

动态规划思路

状态定义：
- dp[i][j] 表示使用前 i 个数字（即 1 到 i）组成的数组中，恰好有 j 个逆序对的数组个数。
状态转移：
- 当我们在前 i-1 个数字的基础上添加第 i 个数字时，第 i 个数字可以放在任意位置。假设第 i 个数字放在第 m 个位置（从 0 开始计数），那么它会与前面的 m 个数字形成逆序对。
- 因此，dp[i][j] 可以通过 dp[i-1][j-m] 转移过来，其中 m 的范围是从 0 到 min(i-1, j)。
初始化：
- dp[0][0] = 1，表示使用 0 个数字时，恰好有 0 个逆序对的数组个数为 1（空数组）。
- 其他 dp[0][j] 均为 0，因为使用 0 个数字时不可能有逆序对。
优化：
- 直接计算 dp[i][j] 时可能会超时，因此我们可以使用前缀和来优化状态转移。

python

class Solusion:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 1000000007
        # 初始化 dp 数组
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        # 动态规划转移
        for i in range(1, n + 1):
            prefix_sum = [0] * (k + 2)
            for j in range(k + 1):
                prefix_sum[j + 1] = (prefix_sum[j] + dp[i - 1][j]) % MOD

            for j in range(k + 1):
                dp[i][j] = (prefix_sum[j + 1] - (prefix_sum[j + 1 - i] if j + 1 - i >= 0 else 0)) % MOD

        return dp[n][k]

代码解释
初始化：
dp = [[0] * (k + 1) for _ in range(n + 1)]：创建一个 (n + 1) x (k + 1) 的二维数组，初始值为 0。
dp[0][0] = 1：使用 0 个数字时，恰好有 0 个逆序对的数组个数为 1。
前缀和数组：
prefix_sum = [0] * (k + 2)：用于存储前缀和，方便快速计算区间和。
for j in range(k + 1): prefix_sum[j + 1] = (prefix_sum[j] + dp[i - 1][j]) % MOD：计算前缀和。
状态转移：
for j in range(k + 1): dp[i][j] = (prefix_sum[j + 1] - (prefix_sum[j + 1 - i] if j + 1 - i >= 0 else 0)) % MOD：使用前缀和优化状态转移。
返回结果：
return dp[n][k]：返回最终结果。
优化说明
前缀和：通过前缀和数组，可以在 O(1) 时间内计算出 dp[i-1][j-m] 的和，从而将时间复杂度从 O(n * k * k) 优化到 O(n * k)。

python

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 1000000007

        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[1][0] = 1
        for i in range(2, n + 1):
            for j in range(min(k, i * (i - 1) // 2) + 1):
                #for x in range(max(0, j - i + 1), j + 1):
                    #dp[i][j] = (dp[i][j] + dp[i - 1][x]) % MOD
                dp[i][j] = ((dp[i][j - 1] if j >= 1 else 0) + dp[i - 1][j] - (dp[i - 1][j - i] if j >= i else 0) + MOD) % MOD

        return dp[n][k]

该代码实现了一个解决 k 个逆序对数组问题的动态规划算法。以下是代码的详细解释：
代码解释
定义常量和初始化 DP 数组：
python
MOD = 1000000007
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[1][0] = 1
MOD 是用来取模的常量，防止结果溢出。
dp 是一个二维数组，dp[i][j] 表示使用 1 到 i 的数字，恰好有 j 个逆序对的数组个数。
初始化 dp[1][0] 为 1，因为只有一个元素时，没有逆序对。
填充 DP 数组：
python
for i in range(2, n + 1):
    for j in range(min(k, i * (i - 1) // 2) + 1):
        dp[i][j] = ((dp[i][j - 1] if j >= 1 else 0) + dp[i - 1][j] - (dp[i - 1][j - i] if j >= i else 0) + MOD) % MOD
外层循环 i 从 2 到 n，表示当前考虑的数字范围是 1 到 i。
内层循环 j 从 0 到 min(k, i * (i - 1) // 2)，表示当前考虑的逆序对数量。
dp[i][j] 的值通过以下公式计算：
dp[i][j - 1] if j >= 1 else 0：前一个逆序对数量的值。
dp[i - 1][j]：不包含当前数字 i 的逆序对数量。
-(dp[i - 1][j - i] if j >= i else 0)：减去多余的部分。
+ MOD：防止负数出现。
% MOD：取模操作，防止结果溢出。
返回结果：
python
return dp[n][k]
返回 dp[n][k]，即使用 1 到 n 的数字，恰好有 k 个逆序对的数组个数。

629.K个逆序对数组 ​

629.K个逆序对数组