給出兩個整數?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]。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/k-inverse-pairs-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題報告：

經典動態規劃。dp[i][j]代表1~i可以構成逆序對為k的方案數。

考慮轉移dp[i][j]，即最后一步決策，即在1~i-1已經放好的基礎上，i放到哪個位置上，放到不同的位置上可以新增0~i-1中的某個值。當然，也不能超了j。即更新dp[i][j]時，決策第i層可以新層逆序對的個數：0~min(i-1, j)。對應加和就行。然后用前綴和優化一下。空間也可以滾動數組優化但是沒啥必要了就不寫了。

AC代碼：

class Solution { public:long long dp[1005][1005];long long sum[1005];const int mod = 1e9 +7;int kInversePairs(int n, int k) {dp[0][0] = 0;for(int i = 1; i<=n; i++) dp[i][0] = 1;for(int i = 1; i<=n; i++) {sum[0] = dp[i-1][0];for(int j = 1; j<=k; j++) {sum[j] = (sum[j-1] + dp[i-1][j])%mod;}for(int j = 1; j<=k; j++) {int down = min(i-1,j);dp[i][j] = (sum[j] - (j-down-1>=0?sum[j-down-1]:0) + mod) % mod;}}return dp[n][k] % mod;} };

TLE代碼：

class Solution { public:long long dp[1005][1005];const int mod = 1e9 +7;int kInversePairs(int n, int k) {dp[0][0] = 0;for(int i = 1; i<=n; i++) dp[i][0] = 1;for(int i = 1; i<=n; i++) {for(int j = 1; j<=k; j++) {for(int q = 0; q<=i-1; q++) {if(j-q < 0) break;dp[i][j] += dp[i-1][j-q];dp[i][j] %= mod;}}}// for(int i = 0; i<=n; i++) {// for(int j = 0; j<=k; j++) {// cout << dp[i][j] << " ";// }// cout <<endl;// } return dp[n][k] % mod;} };

總結

以上是生活随笔為你收集整理的【LeetCode 629】K个逆序对数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。