0903. Valid Permutations for DI Sequence ========================================= 题目信息 -------- :题号: 0903 :难度: Hard :主题: 排列、相邻大小关系、计数 :原题: `LeetCode 0903 `_ :重点: 长度为 ``n`` 的模式约束 ``0`` 至 ``n`` 的排列;``I`` 和 ``D`` 分别规定相邻元素严格递增或严格递减 题目重述 -------- 给定只包含字符 ``I`` 和 ``D`` 的字符串 ``s``,令其长度为 ``n``。考虑由整数 ``0, 1, ..., n`` 各使用恰好一次组成的所有长度为 ``n + 1`` 的排列 ``perm``。 对于每个下标 ``i``:若 ``s[i] == 'I'``,必须满足 ``perm[i] < perm[i + 1]``;若 ``s[i] == 'D'``,必须满足 ``perm[i] > perm[i + 1]``。请返回满足全部相邻关系的排列数量,并对 ``10^9 + 7`` 取模。 ``1 <= s.length <= 200``。 自建示例 -------- 先升后降: .. code-block:: text 输入:s = "ID" 输出:2 解释:需要排列 0、1、2,并满足 perm[0] < perm[1] > perm[2]。合法排列为 [0,2,1] 和 [1,2,0]。 模式长度达到最小值: .. code-block:: text 输入:s = "I" 输出:1 解释:只需排列 0、1,并满足前者小于后者;唯一合法排列是 [0,1]。