★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10608147.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

A valid permutation is a permutation P[0], P[1], ..., 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: 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'}.

我们给出 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. 

示例：

输入："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) 

提示：

1. 1 <= S.length <= 200
2. S 仅由集合 {'D', 'I'} 中的字符组成。

 1 class Solution {
 2     func numPermsDISequence(_ S: String) -> Int {
 3         var n:Int = S.count
 4         var mod:Int = Int(1e9 + 7)
 5         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n + 1),count:n + 1)
 6         for j in 0...n
 7         {
 8             dp[0][j] = 1
 9         }
10         let arrS:[Character] = Array(S)
11         for i in 0..<n
12         {
13             if arrS[i] == "I"
14             {
15                 var j:Int = 0
16                 var cur:Int = 0
17                 while(j < n - i)
18                 {                     
19                     cur = (cur + dp[i][j]) % mod
20                     dp[i + 1][j] = cur
21                     j += 1
22                 }
23             }
24             else
25             {
26                 var j:Int = n - i - 1
27                 var cur:Int = 0
28                 while(j >= 0)
29                 {
30                     cur = (cur + dp[i][j + 1]) % mod
31                     dp[i + 1][j] = cur
32                     j -= 1
33                 }
34             }
35         }
36         return dp[n][0]
37     }
38 }