LeetCode 903 DI 序列的有效排列

Published 3/29/2020
Views 36

我们给出 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)$ 种排列。这里,显然有 ij 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$ 的取值范围: jki1,;S[i1]=D(1.1) j \le k \le i-1,; S[i-1]=D \tag{1.1} 而当 $S[i-1]=I$,则有 $P[i-1] < P[i]$,显然有 0kj1,;S[i1]=I 0 \le k \le j-1, ; S[i-1]=I 因此,我们可以得到转移方程: dp(i,j)={k=ji1dp(i1,k),S[i1]=Dk=0j1dp(i1,k),S[i1]=I(1.2) 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(i,j)={dp(i,j+1)+dp(i1,j),S[i1]=Ddp(i,j1)+dp(i1,j1),S[i1]=I(1.3) 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);
}
0 comments