class Solution {
public:
int numPermsDISequence(string s) {
}
};
903. DI 序列的有效排列
给定一个长度为 n 的字符串 s ，其中 s[i] 是:
“D” 意味着减少，或者“I” 意味着增加有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：
s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；s[i] == 'I'，那么 perm[i] < perm[i+1]。返回 有效排列 perm的数量 。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。
示例 1：
输入：s = "DID" 输出：5 解释： (0, 1, 2, 3) 的五个有效排列是： (1, 0, 3, 2) (2, 0, 3, 1) (2, 1, 3, 0) (3, 0, 2, 1) (3, 1, 2, 0)
示例 2:
输入: s = "D" 输出: 1
提示:
n == s.length1 <= n <= 200s[i] 不是 'I' 就是 'D'原站题解
javascript 解法, 执行用时: 124 ms, 内存消耗: 40.9 MB, 提交时间: 2023-09-28 23:20:43
/**
* @param {string} S
* @return {number}
*/
var numPermsDISequence = function(S) {
let n = S.length
let mod = 1e9 + 7
let dp = [[1], []]
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= i; j++) {
let l = 0, r = j
if (S.charAt(i-1) === 'D') {
l = j, r = i
}
dp[1][j] = 0
for (let k = l; k < r; k++) {
dp[1][j] += dp[0][k]
dp[1][j] %= mod
}
}
[dp[0], dp[1]] = [dp[1], dp[0]]
}
let out = 0
for (let cnt of dp[0]) {
out += cnt
out %= mod
}
return out
}
golang 解法, 执行用时: 44 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-28 23:20:33
func numPermsDISequence(S string) int {
mod := int(1e9 + 7)
n := len(S)
dp := make([][]int, 2)
for i := range dp {
dp[i] = make([]int, n+1)
}
dp[0][0] = 1
for i := 1; i <= n; i++ {
for j := 0; j <= i; j++ {
l, r := 0, j // S[i-1] == 'I'
if S[i-1] == 'D' {
l, r = j, i
}
dp[1][j] = 0
for k := l; k < r; k++ {
dp[1][j] += dp[0][k]
dp[1][j] %= mod
}
}
dp[0], dp[1] = dp[1], dp[0]
}
out := 0
for j := range dp[0] {
out += dp[0][j]
out %= mod
}
return out
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-28 23:19:48
class Solution {
public:
int numPermsDISequence(string S) {
int i, j, size = S.size(), sum = 0, mod = 1000000007;
vector<vector<int>> dp(size + 1, vector<int>(size + 1)); // 令dp[i][j]表示字符串长度为i时，以j为结尾的序列个数
dp[0][0] = 1; // 序列0
for (i = 1; i <= size; ++i) {
if (S[i - 1] == 'D') {
dp[i][i] = 0; // 最后一个数是i，肯定不可能构成降序
for (j = i - 1; j >= 0; --j) {
dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % mod; // 最后一个数是j，那么上一个序列中所有大于等于j结尾的序列都可以构成降序
}
}
else {
dp[i][0] = 0; // 最后一个数是0，肯定不可能构成升序
for (j = 1; j <= i; ++j) {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod; // 最后一个数是j，那么上一个序列中所有小于j结尾的序列都可以构成升序
}
}
}
for (j = 0; j <= size; ++j) {
sum = (sum + dp[size][j]) % mod;
}
return sum;
}
};
python3 解法, 执行用时: 528 ms, 内存消耗: 18.3 MB, 提交时间: 2023-09-28 23:19:09
'''
我们同样可以使用分治算法（实际上是一种区间动态规划）解决这道题目。
首先我们考虑将 0 放在哪里，可以发现 0 要么放在 DI 对应的位置，
要么放在排列的开头且对应的字符为 I，要么放在排列的结尾且对应的字符为 D。将 0 放好后，
排列被分成了 0 左侧和右侧两部分，每个部分各是一个对应长度的有效排列问题。
设左侧的长度为 x，排列的方案数为 f(x)，右侧的长度为 y，排列的方案数为 f(y)，
在合并时，我们需要在 x + y 中选择 x 个数分给左侧，剩余的 y 个数分给右侧，
因此合并后的方案数为 binom(x + y, x) * f(x) * f(y)，其中 binom 为组合数。
'''
from functools import lru_cache
class Solution:
def numPermsDISequence(self, S: str) -> int:
MOD = 10**9 + 7
fac = [1, 1]
for x in range(2, 201):
fac.append(fac[-1] * x % MOD)
facinv = [pow(f, MOD-2, MOD) for f in fac]
def binom(n, k):
return fac[n] * facinv[n-k] % MOD * facinv[k] % MOD
@lru_cache(None)
def dp(i, j):
if i >= j: return 1
ans = 0
n = j - i + 2
if S[i] == 'I': ans += dp(i+1, j)
if S[j] == 'D': ans += dp(i, j-1)
for k in range(i+1, j+1):
if S[k-1:k+1] == 'DI':
ans += binom(n-1, k-i) * dp(i, k-2) % MOD * dp(k+1, j) % MOD
ans %= MOD
return ans
return dp(0, len(S) - 1)
java 解法, 执行用时: 51 ms, 内存消耗: 40.1 MB, 提交时间: 2023-09-28 23:18:12
class Solution {
public int numPermsDISequence(String S) {
int MOD = 1_000_000_007;
int N = S.length();
// dp[i][j] : Num ways to place P_i with relative rank j
int[][] dp = new int[N+1][N+1];
Arrays.fill(dp[0], 1);
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= i; ++j) {
if (S.charAt(i-1) == 'D') {
for (int k = j; k < i; ++k) {
dp[i][j] += dp[i-1][k];
dp[i][j] %= MOD;
}
} else {
for (int k = 0; k < j; ++k) {
dp[i][j] += dp[i-1][k];
dp[i][j] %= MOD;
}
}
}
}
int ans = 0;
for (int x: dp[N]) {
ans += x;
ans %= MOD;
}
return ans;
}
}
python3 解法, 执行用时: 744 ms, 内存消耗: 24.2 MB, 提交时间: 2023-09-28 23:17:57
'''
动态规划
当我们已经确定了排列中的前 i 个元素 P[0], P[1], ..., P[i - 1] 时，
我们需要通过字符串 S 的第 i - 1 位 S[i - 1] 和 P[i - 1] 共同确定下一个元素 P[i]。
这说明，P[i - 1] 之前的元素 P[0], P[1], .., P[i - 2] 都是无意义的，
有意义的是 P[i - 1] 和剩下未选出的 n + 1 - i 个元素的相对大小。
例如当 n 的值为 5 时，我们已经确定的排列为 2, 3, 4，未选择的元素为 0, 1, 5，
那么有意义的状态是排列 ?, ?, 2 以及未选择的元素 0, 1, 3，
其中 ? 表示我们不关心的元素，0, 1, 2, 3 表示 P[i - 1] 和未选择元素的相对大小。
这样我们就可以用动态规划解决这道题目。
我们用 dp(i, j) 表示确定了排列中到 P[i] 为止的前 i + 1 个元素，
并且 P[i] 和未选择元素的相对大小为 j 的方案数（即未选择的元素中，有 j 个元素比 P[i] 小）。
在状态转移时，dp(i, j) 会从 dp(i - 1, k) 转移而来，其中 k 代表了 P[i - 1] 的相对大小。
如果 S[i - 1] 为 D，那么 k 不比 j 小；如果 S[i - 1] 为 I，那么 k 必须比 j 小。
'''
from functools import lru_cache
class Solution:
def numPermsDISequence(self, S: str) -> int:
MOD = 10**9 + 7
N = len(S)
@lru_cache(None)
def dp(i, j):
# How many ways to place P_i with relative rank j?
if i == 0:
return 1
elif S[i-1] == 'D':
return sum(dp(i-1, k) for k in range(j, i)) % MOD
else:
return sum(dp(i-1, k) for k in range(j)) % MOD
return sum(dp(N, j) for j in range(N+1)) % MOD
'''
我们发现，在上面动态规划的状态转移中，当 S[i - 1] 为 I 时，
dp(i, j) 比 dp(i, j - 1) 多出了 dp(i - 1, j - 1) 这一项；
当 S[i - 1] 为 D 时，dp(i, j) 比 dp(i, j + 1) 多出了 dp(i - 1, j) 这一项，
因此可以不用 dp(i, j) 都计算一遍对应的 dp(i - 1, k) 的和，而是用
dp(i, j) = dp(i, j - 1) + dp(i - 1, j - 1) if S[i - 1] == 'I'
dp(i, j) = dp(i, j + 1) + dp(i - 1, j) if S[i - 1] == 'D'
'''
def numPermsDISequence2(self, S: str) -> int:
MOD = 10**9 + 7
N = len(S)
@lru_cache(None)
def dp(i, j):
# How many ways to place P_i with relative rank j?
if not(0 <= j <= i):
return 0
if i == 0:
return 1
elif S[i-1] == 'D':
return (dp(i, j+1) + dp(i-1, j)) % MOD
else:
return (dp(i, j-1) + dp(i-1, j-1)) % MOD
return sum(dp(N, j) for j in range(N+1)) % MOD