难度: Hard
给定一个长度为 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'运行时间: 40 ms
内存: 16.0 MB
class Solution:
def numPermsDISequence(self, s: str) -> int:
mod = 10**9 + 7
n = len(s)
f = [1] + [0] * n
for i, c in enumerate(s, 1):
pre = 0
g = [0] * (n + 1)
if c == "D":
for j in range(i, -1, -1):
pre = (pre + f[j]) % mod
g[j] = pre
else:
for j in range(i + 1):
g[j] = pre
pre = (pre + f[j]) % mod
f = g
return sum(f) % mod
这个题解采用动态规划的方法。定义 f[i][j] 表示前 i 个字符构成的子序列中，以 j 结尾的有效排列数量。为了简化空间复杂度，使用一维数组 f[j] 不断更新来表示当前的状态，并用辅助数组 g[j] 来计算更新。对于每一个字符，根据是 'D' 还是 'I'，决定填充的方向和方式。如果是 'D'，从后向前更新 g[j]，累积前面的 f[j] 值确保递减；如果是 'I'，从前向后更新 g[j]，累积前面的 f[j] 值以保证递增。最后，将 g 赋值回 f 进行下一轮的计算。计算结束后，f 数组的累加和就是所求的答案。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def numPermsDISequence(self, s: str) -> int:
mod = 10**9 + 7 # 定义模数
n = len(s) # 输入字符串的长度
f = [1] + [0] * n # 初始化 f 数组，f[0] 设为 1，其余为 0
for i, c in enumerate(s, 1): # 遍历字符串 s 的每个字符
pre = 0 # 初始化前缀和
g = [0] * (n + 1) # 初始化 g 数组
if c == "D": # 如果当前字符是 'D'
for j in range(i, -1, -1): # 从 i 到 0 更新 g
pre = (pre + f[j]) % mod # 更新前缀和
g[j] = pre # 设置 g[j] 为当前的前缀和
else: # 如果当前字符是 'I'
for j in range(i + 1): # 从 0 到 i 更新 g
g[j] = pre # 设置 g[j] 为当前的前缀和
pre = (pre + f[j]) % mod # 更新前缀和
f = g # 把 g 赋值给 f，为下一轮做准备
return sum(f) % mod # 返回 f 数组的元素之和模 10^9+7
在动态规划中，数组f用于记录各种排列的数量。初始设置为[1] + [0] * n的目的是为了表示在序列开始之前，存在一个虚拟的起点，且这个起点唯一确定无其他选择。因此，f[0]设置为1表示只有一个方式填充到序列的第一个位置，而其他位置f[1]到f[n]初始化为0，因为在没有任何输入字符处理前，这些位置无法形成任何有效的排列。
在处理字符'D'时，要求序列递减，因此需要从后向前更新g数组，这样可以确保在填充时，每个位置的值都是基于之前所有可能的较大值的累加，从而满足递减的条件。相反，在处理字符'I'时，要求序列递增，因此需要从前向后更新g数组，这样可以确保在填充时，每个位置的值都是基于之前所有可能的较小值的累加，从而满足递增的条件。这种迭代方向的选择是为了正确地反映'D'和'I'对序列增长方向的要求。
在动态规划中，前缀和pre用于累积f数组中的值，以便于计算g数组。对于字符'D'，pre累积从当前位置往前的所有f[j]的值，确保当填充到任何一个位置j时，g[j]能反映所有可能的、比j大的位置的排列数之和。对于字符'I'，则反之，pre累积到当前位置之前所有的f[j]的值，确保每个位置j的g[j]能包含所有可能的、比j小的位置的排列数之和。这样，pre帮助在保持状态转移的连续性和正确性的同时，高效地更新g数组。
在遍历完所有字符后，f数组中的每个元素f[j]代表以数字j结尾的所有有效排列的数量。因此，将f数组中所有元素求和，就得到了满足给定DI序列的所有可能排列的总数。由于结果可能非常大，为了防止溢出并满足题目要求，我们需要对结果取模10^9+7，这是一个常用的大素数，用于保持计算在安全的整数范围内。