1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

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

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，状态定义。dp[i][j]表示包含1到i的数字且恰好拥有j个逆序对的不同数组的个数。

第二步，状态初始化。dp[0][0]=1，表示不用任何数构建一个空数组，逆序对数量为0的一种情况。

第三步，状态转移。假设有从1到i的序列，枚举最后一个元素为p的序列，逆序对可以分为两部分，一部分由p和p+1到i部分进行两两组成，另一部分由1到p-1和p+1到i的元素内部进行组成，由于只考虑相对大小，所以这就是一个规模为i-1的子问题。所以由递推公式：dp[i][j]=sum(dp[i-1][j-(i-p)] for p in range(1,i+1))=sum(dp[i-1][j-p] for p in range(0,i))。同理可得dp[i][j-1]=sum(dp[i-1][j-p-1] for p in range(0,i))，可以看出dp[i][j-1]部分是在dp[i][j]中，dp[i][j]=dp[i][j-1]-dp[i-1][j-i]+dp[i-1][j]

• 这里的dp[i][j]=dp[i][j-1]-dp[i-1][j-i]+dp[i-1][j]，可以看出dp[i][j]只依赖dp[i]和dp[i-1]，所以可以将状态数组降为一维

第四步，最终的dp[n][k]即为题解。

3.解题代码

python代码

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # 思路3：动态规划-优化至时间复杂度O(nk)，空间复杂度O(n)
        MOD = 10 ** 9 + 7
        dp = [0] * (k + 1)
        dp[0] = 1
        # > 状态转移。从思路2中的dp[i][j]=dp[i][j-1]-dp[i-1][j-i]+dp[i-1][j]，可以看出dp[i][j]只依赖dp[i]和dp[i-1]，所以可以将状态数组降为一维
        for i in range(1, n + 1):
            dp2 = [0] * (k + 1)
            for j in range(k + 1):
                dp2[j] = dp[j]
                if j > 0:
                    dp2[j] = (dp2[j] + dp2[j - 1]) % MOD
                if j >= i:
                    dp2[j] = (dp2[j] - dp[j - i]) % MOD
            dp = dp2
        # print(dp)
        # 最终的dp[k]即为题解。
        return dp[k]
    
    def kInversePairs2(self, n: int, k: int) -> int:
        # 思路2：动态规划-优化至时间复杂度O(nk)，空间复杂度O(n^2)
        MOD = 10 ** 9 + 7
        # 第一步，状态定义。dp[i][j]表示包含1到i的数字且恰好拥有j个逆序对的不同数组的个数。
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        # 第二步，状态初始化。dp[0][0]=1，表示不用任何数构建一个空数组，逆序对数量为0的一种情况。
        dp[0][0] = 1
        # 第三步，状态转移。假设有从1到i的序列，枚举最后一个元素为p的序列，逆序对可以分为两部分，一部分由p和p+1到i部分进行两两组成，另一部分由1到p-1和p+1到i的元素内部进行组成，由于只考虑相对大小，所以这就是一个规模为i-1的子问题。所以由递推公式：dp[i][j]=sum(dp[i-1][j-(i-p)] for p in range(1,i+1))=sum(dp[i-1][j-p] for p in range(0,i))。同理可得dp[i][j-1]=sum(dp[i-1][j-p-1] for p in range(0,i))，可以看出dp[i][j-1]部分是在dp[i][j]中，dp[i][j]=dp[i][j-1]-dp[i-1][j-i]+dp[i-1][j]
        for i in range(1, n + 1):
            for j in range(k + 1):
                dp[i][j] = dp[i - 1][j]
                if j > 0:
                    dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD
                if j >= i:
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i]) % MOD
        # print(dp)
        # 第四步，最终的dp[n][k]即为题解。
        return dp[n][k]

c++代码

class Solution {
private:
    const int MOD = 1000000007;
public:
    int kInversePairs(int n, int k) {
        vector<int> dp(k + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            vector<int> dp2(k + 1, 0);
            for (int j = 0; j <= k; j++) {
                dp2[j] = dp[j] % MOD;
                if (j > 0) {
                    dp2[j] = (dp2[j] + dp2[j - 1]) % MOD;
                }
                if (j >= i) {
                    dp2[j] = (dp2[j] - dp[j - i] + MOD) % MOD;
                }
            }
            dp = move(dp2);
        }
        return dp[k];
    }
};

4.执行结果