## 903. Valid Permutations for DI Sequence

We are given `S`, a length `n` string of characters from the set `{'D', 'I'}`. (These letters stand for "decreasing" and "increasing".)

valid permutation is a permutation `P, P, ..., P[n]` of integers `{0, 1, ..., n}`, such that for all `i`:

• If `S[i] == 'D'`, then `P[i] > P[i+1]`, and;
• If `S[i] == 'I'`, then `P[i] < P[i+1]`.

How many valid permutations are there?  Since the answer may be large, return your answer modulo `10^9 + 7`.

Example 1:

```Input: "DID"
Output: 5
Explanation:
The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
```

Note:

1. `1 <= S.length <= 200`
2. `S` consists only of characters from the set `{'D', 'I'}`.

## Rust Solution

``````struct Solution;

const MOD: i64 = 1_000_000_007;

impl Solution {
fn num_perms_di_sequence(s: String) -> i32 {
let n = s.len();
let s: Vec<char> = s.chars().collect();
let mut memo = vec![vec![-1; n + 1]; n + 1];
for j in 0..=n {
memo[n][j] = 1;
}
Self::dp(0, 0, &mut memo, &s, n) as i32
}

fn dp(i: usize, j: usize, memo: &mut Vec<Vec<i64>>, s: &[char], n: usize) -> i64 {
if memo[i][j] != -1 {
memo[i][j]
} else {
let mut res = 0;
if s[i] == 'I' {
for k in j + 1..=i + 1 {
res += Self::dp(i + 1, k, memo, s, n);
res %= MOD;
}
}
if s[i] == 'D' {
for k in 0..=j {
res += Self::dp(i + 1, k, memo, s, n);
res %= MOD;
}
}
memo[i][j] = res;
res
}
}
}

#[test]
fn test() {
let s = "DID".to_string();
let res = 5;
assert_eq!(Solution::num_perms_di_sequence(s), res);
let s = "D".to_string();
let res = 1;
assert_eq!(Solution::num_perms_di_sequence(s), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.