LeetCode刷题实战629：K个逆序对数组-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 K个逆序对数组，我们先来看题面：

https://leetcode.cn/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 109 + 7.

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

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

由于答案可能很大，只需要返回答案 mod 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 个逆序对。

解题

https://blog.csdn.net/weixin_44171872/article/details/112098935

主要思路：

（1）动态规划；

（2）dp[ i ][ j ]表示i个数时，组成 j 个逆序对时，有多少种方法，对于第 i 个数，可以在原数组中插入不同的位置，从而增加0,1，……，i-1个逆序对，故dp[ i ][ j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]+……+dp[i -1][ j-(i-1)];

（3）又有dp[ i ][ j - 1]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+……+dp[i -1][ j-i];，则两个式子相减有 dp[ i ][ j ]-dp[ i ][ j-1 ]=dp[i-1][ j ]-dp[ i-1 ][ j-i]; 既dp[ i ][ j ]=dp[ i ][ j-1 ]+dp[i-1][ j ]-dp[ i-1 ][ j-i];

class Solution {
public:
    int kInversePairs(int n, int k) {
        vector<vector<long>> dp(n+1,vector<long>(k+1,0));
        for(int i=1;i<=n;++i){//初始化，没有逆序的情形
            dp[i][0]=1;
        }
        for(int i=2;i<=n;++i){
            for(int j=1;j<=k;++j){
                if(j>=i){//对于 j>=i 
                    dp[i][j]=dp[i][j-1]+(dp[i-1][j]+1000000007-dp[i-1][j-i]);
                }
                else{
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];//少了上述的一项
                }
                dp[i][j]%=1000000007;
            }
        }
        return dp[n][k];
    }
};