Description

给定$n$和$k$，求包含数字$1\dots n$且恰好有$k$个逆序对的数组方案数。答案对${10}^9+7$取模

Constraints

• $1\le n\le 1000$
• $0\le k\le 1000$

Solution

设$dp[i][j]$为使用$1\dots i$构成长度$i$的数组，且恰有$j$个逆序对的方案数。这里下标从1开始算起

问题在于怎么做状态转移

如果算出$dp[i-1]$的答案，把数字$i$插入到原$1\dots i-1$中，则得到$dp[i]$

而不同位置会产生不同的逆序对，其增加的数目显然在$[0,i-1]$内

因此有：$dp[i][j]=\sum _{k=0}^{i-1}dp[i-1][j-k]$

而这个式子直接算的话需要$O(n^{2}k)$，显然超时，因此加一个前缀和降低复杂度到$O(nk)$

Note: 如果集合为空，则方案数设为0（$i==0$）

Code

class Solution {
public:
    int kInversePairs(int n, int k) {
        auto dp = vector<vector<long>>(2, vector<long>(k+1));
        auto pre = dp;
        constexpr long MOD = 1e9 + 7;
        for(int i = 1; i <= n; ++i) {
            dp[i & 1][0] = pre[i & 1][0] = 1;
            for(int j = 1; j <= k; ++j) {
                auto sum = pre[i-1 & 1][j];
                if(j-i >= 0) sum -= pre[i-1 & 1][j-i];
                dp[i & 1][j] = (sum + MOD) % MOD;
                pre[i & 1][j] = (pre[i & 1][j-1] + dp[i & 1][j]) % MOD;
            }
        }
        return dp[n & 1][k];
    }
};

Link

LeetCode-629 K Inverse Pairs Array