資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中 DI 序列的有效排列
假設我們有一個字串 S。這是一個來自集合 {'D', 'I'} 的字元字串。（D 表示“遞減”而 I 表示“遞增”）
現在考慮一個有效排列是整數 {0 到 n} 的排列 P[0]、P[1]、…、P[n]，使得對於所有 i，它滿足以下規則
如果 S[i] == 'D'，則 P[i] > P[i+1]；
否則當 S[i] == 'I' 時，則 P[i] < P[i+1]。
我們必須找到有多少個有效的排列？答案可能非常大，因此我們將使用模 10^9 + 7 返回。
因此，如果輸入類似於“IDD”，則輸出將為 3，因此將有三個不同的排列，它們類似於 (0,3,2,1)、(1,3,2,0)、(2,3,1,0)。
為了解決這個問題，我們將遵循以下步驟 -
n := S 的大小
定義一個大小為 (n + 1) x (n + 1) 的二維陣列 dp
用於初始化 j := 0，當 j <= n 時，更新（增加 j 1），執行 -
dp[0, j] := 1
用於初始化 i := 0，當 i < n 時，更新（增加 i 1），執行 -
如果 S[i] 與 'I' 相同，則 -
用於初始化 j := 0，curr := 0，當 j < n - i 時，更新（增加 j 1），執行 -
curr := (dp[i, j] + curr) mod m
dp[i + 1, j] = (dp[i + 1, j] + curr)
否則
用於初始化 j := n - i - 1，curr := 0，當 j >= 0 時，更新（減少 j 1），執行 -
curr := (dp[i, j + 1] + curr) mod m
dp[i + 1, j] = (dp[i + 1, j] + curr)
返回 dp[n, 0]
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int numPermsDISequence(string S) {
int n = S.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int j = 0; j <= n; j++)
dp[0][j] = 1;
for (int i = 0; i < n; i++) {
if (S[i] == 'I') {
for (int j = 0, curr = 0; j < n - i; j++) {
curr = (dp[i][j] + curr) % m;
dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
}
} else {
for (int j = n - i - 1, curr = 0; j >= 0; j--) {
curr = (dp[i][j + 1] + curr) % m;
dp[i + 1][j] = (dp[i + 1][j] + curr) % m;
}
}
}
return dp[n][0];
}
};
main(){
Solution ob;
cout << (ob.numPermsDISequence("IDD"));
}輸入
"IDD"
輸出
3
677 次檢視
