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.

示例：

输入："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 <= S.length <= 200
S 仅由集合 {'D', 'I'} 中的字符组成。

思路分析：

我们用 dp(i, j) 表示确定了排列中到 P[i] 为止的前 i + 1 个元素，并且 P[i] 和未选择元素的相对大小为 j 的方案数（即未选择的元素中，有 j 个元素比 P[i] 小）。在状态转移时，dp(i, j) 会从 dp(i - 1, k) 转移而来，其中 k 代表了 P[i - 1] 的相对大小。如果 S[i - 1] 为 D，那么 k 不比 j 小；如果 S[i - 1] 为 I，那么 k 必须比 j 小。

代码：

 class Solution {

 public:

     int mod = 1e9+;

     int numPermsDISequence(string S) {

         int n = S.size();

         if(n==)

             return ;

         vector<vector<int>> dp(n+, vector<int>(n+, ));

         for(int i=; i<n+; i++)

             dp[][i]=;

         for(int i=; i<=n; i++)

         {

             for(int j=; j<=i; j++)

             {

                 if(S[i-]=='D')

                 {

                     for(int k=j; k<i; k++)

                     {

                         dp[i][j] += dp[i-][k];

                         dp[i][j] %= mod;

                     }

                 }

                 else

                 {

                     for(int k=; k<j; k++)

                     {

                         dp[i][j] += dp[i-][k];

                         dp[i][j] %= mod;

                     }

                 }

             }

         }

         int ans = ;

         for(int i=; i<=n; i++)

         {

             ans += dp[n][i];

             ans %= mod;

         }

         return ans;

     }

 };

巴特西

leetcode 903. DI序列的有效排列

最新文章

热门文章