629 K个逆序对数组（动态规划）

旧城等待， 2022-09-02 00:53 84阅读 0赞

**1. 问题描述：**

给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a\[i\] > a\[j\]，则其为一个逆序对；否则不是。由于答案可能很大，只需要返回答案 mod 10 ^ 9 + 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\]。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/k-inverse-pairs-array

**2. 思路分析：**

分许题目可以知道这是一道关于dp的题目（dp的题目一般是数据范围小于等于1000并且需要求解所有方案数目）。对于动态规划的题目我们一般是考虑两个步骤：① 状态表示 ② 状态计算；这是一道比较常规的动态规划题目所以我们根据题目的描述定义dp数组即可，由题可知我们可以定义一个二维的dp数组，其中dp\[i\]\[j\]表示所有由1~i构成包含j个逆序对的所有排列对应的方案数目，状态表示按照了题目表达的意思定义的所以也比较好理解，怎么样进行状态的计算呢？对于状态计算一般是将dp\[i\]\[j\]划分若干个不同的集合，通过集合中的前一个状态计算出当前的状态，对于集合的划分我们一般是找最后一个不同点，可以发现我们可以枚举当前的数字i放到前一个排列中0，1，2...i - 1的位置，这样在包含数字1~i-1的上一个排列的基础上增加的逆序对的数目为i - 1，i - 2，... 0，为了避免重复枚举某些状态，这里我们可以在遍历的时候维护上一个状态的值，可以使用两层循环进行枚举，第一层循环枚举当前的数字的个数，也即1~i，第二层循环枚举当前i个数字逆序对的个数，其实表达的意思是尝试将i放到上一个状态的某个排列中的对应位置上（dp中的每一个状态表示的就是对应的排列），并且可以发现dp\[i\]\[j + 1\]比dp\[i\]\[j\]少了一项，多了另外的一项，所以我们在遍历的时候维护上一个到目前为止dp\[i\]\[j\]的和，并且减去多余的项这样就可以在遍历的时候直接计算出当前的dp\[i\]\[j\]，这样就可以在遍历的时候直接计算出dp\[i\]\[j\]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

from typing import List
    
    class Solution:
        def kInversePairs(self, n: int, k: int) -> int:
            mod = 10 ** 9 + 7
            dp = [[0] * (k + 1) for i in range(n + 1)]
            # 初始状态, 只有一个数字的逆序对为1
            dp[1][0] = 1
            for i in range(2, n + 1):
                s = 0
                for j in range(k + 1): 
                    s += dp[i - 1][j]
                    # 因为多出来的是最小的那一项, 并且j进入了循环的下一次的时候那么应该是j - i而不是j - (i - 1)
                    # 在减去多余的项的时候其实减去的上一个dp[i][j]中最后剩余的那一项, 并且只有当上一个状态加上了剩余的那个状态的时候才需要减去也即存在才减去
                    if j - i >= 0: s -= dp[i - 1][j - i]
                    dp[i][j] = s % mod
            return (dp[n][k] + mod) % mod

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/0464817c8ae745eaaebe9e5df384e2f4.png