629. K个逆序对数组--（每日一难phase2--days11）

629. K个逆序对数组

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

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

由于答案可能很大，只需要返回 答案 mod 1e9 + 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]。

解析：

• n个数组合，可以看作n-1个数组合，然后添加了一个数字n
• 添加了一个更大数字将会带来什么影响呢？再1-n-1添加n，n的可以放在n个位置上。例如：1 2 3 添加4， 4 1 2 3，1 4 2 3， 1 2 4 3 , 1 2 3 4. 则由逆序对范围为0–>n-1对。
• 用f[n][k]表示n个数产生逆序对为k的最大对数。则f[n][k]=f[n-1][k+1-n]+…+f[n][k] (由于当前增加的最大的逆序对为n-1个，也就是说n-1时只有满足x+n-1=k时，才可以产生k个逆序对，因此，x=k+1-n)。所以f[n][k]可以由**f[n][k]=f[n-1][k+1-n]+…+f[n][k]**求得。
• 由于n个数只与n-1有关，因此可以将2维dp转化为1维，需要注意的是求f[k]时需要从大到小求取----具体看代码。
• 求 f[n][k]=f[n-1][k+1-n]+…+f[n-1][k].
• 求f[n][k-1]=f[n-1][k-1+1-n]+…+f[n-1][k-1]
• f[n][k-2]…都需要n-1列值相加，因此可以使用前缀和优化时间

class Solution {
    long long mod=1e9+7;
public:
    int kInversePairs(int n, int k) {
        if(k==0)
            return 1;
        int f[n+1][k+1];
        memset(f,0,sizeof(f));
        for(int i=0;i<=n;i++){
            f[i][0]=1;
        }
        for(int i=2;i<=n;i++){
        	// 需要将i位置所有状态都求出（转移到i+1需要使用）
            for(int j=0;j<=k;j++){
            	// 加上i之后最小可以凑成j对逆序对的起始位置
                int down=max(0,j+1-i);
                long long tmp=0;
                //可以看出i维只与i-1有关；
                for(int m=down;m<=j;m++){
                    tmp+=f[i-1][m];
                    tmp%=mod;
                }
                f[i][j]=tmp;
            }
        }
        return f[n][k];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 空间优化

class Solution {
    long long mod=1e9+7;
public:
    int kInversePairs(int n, int k) {
        if(k==0)
            return 1;
        int f[k+1];
        fill(f,f+k+1,0);
   		// 一个数时，逆序对为0的最大逆序对为1
        f[0]=1;
        for(int i=2;i<=n;i++){
        	// 需要从大到小，因为求取较大j时需要前边值（如果前边修改了）
            for(int j=k;j>=0;j--){
                int down=max(0,j+1-i);
                long long tmp=0;
                for(int m=down;m<=j;m++){
                    tmp+=f[m];
                    tmp%=mod;
                }
                f[j]=tmp;
            }
        }
        return f[k];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 时间优化

class Solution {
    long long mod=1e9+7;
public:
    int kInversePairs(int n, int k) {
        if(k==0)
            return 1;
        long long f[k+1];
        fill(f,f+k+1,0);
        f[0]=1;
        for(int i=2;i<=n;i++){
        	// 用前缀和代替每次循环累加，降低时间复杂度
            for(int h=1;h<=k;h++){
                f[h]+=f[h-1];
                f[h]%=mod;
            }
            for(int j=k;j>=0;j--){
                int down=max(0,j+1-i);
                /*long long tmp=0;
                for(int m=down;m<=j;m++){
                    tmp+=f[m];
                    tmp%=mod;
                }*/
                // 可能后边的f[j]取模，前边f[down-1]没有取模，这一样就会产生负数结果
                // 可以使用先将f[j]+mod,然后结果%mod技巧。
                if(down>0)
                    f[j]-=f[down-1]-mod,f[j]%=mod;
            }
        }
        return f[k];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31