LeetCode 903 DI 序列的有效排列

我们给出 S，一个源于 {'D', 'I'} 的长度为 n 的字符串 。（这些字母代表 “减少” 和 “增加”。） 有效排列 是对整数 {0, 1, ..., 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-permutations-for-di-sequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题可以用动态规划解决，考虑这样的状态 $\left(i, j\right)$：

当完成前 $i+1$ 个排列时（$P[0], P[1], \cdots, P[i]$），最后一位数字在其中是 第 $j$ 小的（即，$i+1$ 个数字中，有 $j$ 个比 $P[j]$ 小）。

计这样的状态我们可以找到 $dp(i,j)$ 种排列。这里，显然有 $$i \ge j$$ 注意到这里我们并没有关心前 $i+1$ 个数字的具体取值，因为我们只关心它们的相对顺序。

转移方程

那么状态 $(i,j)$ 可以从哪些状态得到呢？显然，可以从 $(i-1, k)$ 状态中得到，其中 $k$ 的取值范围是我们所关心的。这里我们需要结合字符串 $S$ 考虑。

当 $S[i-1] = D$ ，则有 $P[i-1] > P[i]$，而我们已知前 $i+1$ 个数字中有 $j$ 个比 $P[i]$ 更小，因此除去 $P[i]$ 后，至少有 $j$ 个数字比 $P[i-1]$ 更小。而注意到我们此时只有 $i$ 个数字，因此很容易确定 $k$ 的上界。容易得到 $k$ 的取值范围： $$j \le k \le i-1,; S[i-1]=D \tag{1.1}$$ 而当 $S[i-1]=I$，则有 $P[i-1] < P[i]$，显然有 $$0 \le k \le j-1, ; S[i-1]=I$$ 因此，我们可以得到转移方程： $$dp\left( i,j \right) =\begin{cases} \sum\limits_{k=j}^{i-1}{dp\left( i-1,k \right)},& S\left[ i-1 \right] =D \\ \sum\limits_{k=0}^{j-1}{dp\left( i-1,k \right)},& S\left[ i-1 \right] =I \\ \end{cases} \tag{1.2}$$

DP 优化

注意到公式 $(1.2)$ 中，只出现了 $i$ 和 $i-1$，因此我们可以对内存进行优化，只保留一个一维数组 $dp[j]$ 即可。

另外注意到，公式 $(1.2)$ 实际上是前缀和形式，因此我们可以使用前缀和优化： $$dp\left( i,j \right) =\begin{cases} dp\left( i,j+1 \right) +dp\left( i-1,j \right) ,& S\left[ i-1 \right] =D \\ dp\left( i,j-1 \right) +dp\left( i-1,j-1 \right) ,& S\left[ i-1 \right] =I \\ \end{cases} \tag{1.3}$$ 公式 $(1.3)$ 将时间优化为 $O(N^2)$，内存优化为 $O(N)$。

代码实现（rust）

impl Solution {
    pub fn num_perms_di_sequence(s: String) -> i32 {
        const MOD: i32 = 1_000_000_000 + 7;
        let n = s.len();

        let s_chars: Vec<char> = s.chars().collect();
        let mut dp = vec![0; 1];
        // i=0, dp(0, 0) = 1
        dp[0] = 1;
        for i in 1..n + 1 {
            // j in [0, i]
            let mut new_dp = vec![0; i + 1];
            match s_chars[i - 1] {
                'D' => {
                    // skip j=i (default as 0)
                    for j in (0..i).rev() {
                        new_dp[j] = (new_dp[j + 1] + dp[j]) % MOD;
                    }
                }
                'I' => {
                    // skip j=0 (default as 0)
                    for j in 1..i + 1 {
                        new_dp[j] = (new_dp[j - 1] + dp[j - 1]) % MOD;
                    }
                }
                _ => unreachable!(),
            }
            dp = new_dp;
        }

        dp.into_iter().fold(0, |a, b| (a + b) % MOD)
    }
}

#[test]
fn test_solution() {
    macro_rules! test {
        ($n:expr, $ans:expr) => {
            assert_eq!(Solution::num_perms_di_sequence($n.to_owned()), $ans);
        };
    }
    test!("D", 1);
    test!("DD", 1);
    test!("DID", 5);
    test!("DDDDDDDDD", 1);
    test!("DIDDDDIID", 3629);
    test!("IDDDIIDIIIIIIIIDIDID", 853197538);
}