629. K個逆序對數組

給出兩個整數 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 個逆序對。

說明:

• n 的范圍是 [1, 1000] 并且 k 的范圍是 [0, 1000]。

解題思路

狀態轉移公式的推導

例如當n=3 ，k=2時，xxx代表n=3時的逆序對數組的任意情況，我們需要計算n=4并且k=2的情況，可以看成是向n=3時的所有逆序對數組插入值4，下面是插入的幾種情況

1. 4xxx，因為4是當前的最大值，必然大于后面3個元素，所以能產生3對逆序對，超出了k=2
2. x4xx，因為4是當前的最大值，必然大于后面2個元素，所以必然能產生2對逆序對，又因為我們需要逆序對的數量k=2，所以只能從n=2，k=0的情況轉移而來
3. xx4x，因為4是當前的最大值，必然大于后面1個元素，所以必然能產生1對逆序對，又因為我們需要逆序對的數量k=2，所以只能從n=2，k=1的情況轉移而來
4. xxx4，因為4在最末尾，所以不能產生新的逆序對，又因為我們需要逆序對的數量k=2，所以只能從n=2，k=2的情況轉移而來

因此我們可以得出
dp[n+1][k]=dp[n][k-1]+dp[n][k-2]…dp[n][k-n+1]

使k=k+1得
dp[n+1][k+1]=dp[n][k]+dp[n][k-1]…dp[n][k-n+2]

兩式相減得：dp[n][k]=dp[n-1][k]+dp[n][k-1]-dp[n-1][k-n]

代碼

class Solution {
public:int kInversePairs(int n, int k) {vector<vector<int>> dp(n+1,vector<int>(k+1,0));dp[1][0]=1;int mod=1000000007;for (int i = 2; i <=n; ++i) {for (int j = 0; j <=k; ++j) {dp[i][j]=dp[i-1][j]+(j-1>=0?dp[i][j-1]:0)-(j-i>=0?dp[i-1][j-i]:0);if (dp[i][j]>=mod)dp[i][j]-=mod;else if (dp[i][j]<0)dp[i][j]+=mod;}}return dp[n][k];}
};