Skip to content

793. K Inverse Pairs Array

793. K Inverse Pairs Array

题目: https://leetcode.com/problems/k-inverse-pairs-array

难度: Hard

题意：

  1. 给定一个数n和一个数k
  2. 求n个元素，逆序对数等于k的序列数

思路：

  • 最容易想到的是动态规划
  • 我们一个数一个数丢进去，假设已经存在n-1个元素的序列，我们要放一个比他们都小的数，这时候根据插入的位置不同就会产生0到(n-1)的逆序对数
  • 设dp[n][k]表示n个元素，逆序对数等于k的序列数，有状态转移方程dp[n][k]=sum{dp[n-1][k - (0..(n-1))]}
  • 如果直接求的话，复杂度是o(n^3)
  • 注意观察算dp[n][k]，用到的是dp[n-1][k]到dp[n-1][k-(n-1)]，算dp[n][k-1]，用到的是dp[n-1][k-1]到dp[n-1][k-1-(n-1)]，于是我们可以保存这个和，然后算dp[n][i]的时候只需要加一个数减一个数就可以维护这个和
  • 复杂度是o(n^2)

解法：

#include<cstdio>
#include<cstring>

class Solution {
public:
    int a[1001][1001];
    int MOD = 1000000007;
    int kInversePairs(int n, int k) {
        memset(a, 0, sizeof(a));
        a[0][0] = 1;
        for (int i = 1;i <= n;i++) {
            int s = 0;
            for (int j = 0;j <= k;j++) {
                s += a[i - 1][j];
                if (s >= MOD) {
                    s -= MOD;
                }
                if (j - i >= 0) {
                    s -= a[i - 1][j - i];
                    if (s < 0) {
                        s += MOD;
                    }
                }
                a[i][j] = s;
            }
        }
        return a[n][k];
    }
};
回到顶部