資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中 K 逆序對陣列
假設我們有兩個整數 n 和 k，我們需要找到有多少個不同的陣列由 1 到 n 的數字組成，並且正好有 k 個逆序對。對於陣列中的第 i 個和第 j 個元素，如果 i < j 且 a[i] > a[j]，則稱為逆序對。這裡答案可能非常大，答案應該模 $10^{9}$ + 7。
因此，如果輸入類似於 n = 3 和 k = 1，則輸出將為 2，因為陣列 [1,3,2] 和 [2,1,3] 將只有一個逆序對。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個大小為 (n + 1) x (k + 1) 的二維陣列 dp
- dp[0, 0] := 1
- 初始化 i := 1，當 i<= n 時，更新（i 增加 1），執行：
- dp[i, 0] := 1
- 初始化 j := 1，當 j <= k 時，更新（j 增加 1），執行：
- dp[i, j] := dp[i, j - 1] + dp[i – 1, j]
- dp[i, j] := dp[i, j] mod m
- 如果 j >= i，則：
- dp[i, j] := (dp[i, j] - dp[i – 1, j - i] + m) mod m
- 返回 dp[n, k]
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int kInversePairs(int n, int k) {
vector < vector <int> > dp(n + 1, vector <int>(k + 1));
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
dp[i][0] = 1;
for(int j = 1; j <= k; j++){
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
dp[i][j] %= m;
if(j >= i){
dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + m) % m;
}
}
}
return dp[n][k];
}
};
main(){
Solution ob;
cout << (ob.kInversePairs(4,2));
}輸入
4 2
輸出
5
更新於: 2020-06-01
226 次瀏覽
廣告