0903：DI 序列的有效排列（2433 分）

力扣第 101 场周赛第 4 题

题目

给定一个长度为 n 的字符串 s ，其中 s[i] 是:

• “D” 意味着减少，或者
• “I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

• 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
• 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列 perm的数量 。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。

示例 1：

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

示例 2:

输入: s = "D"
输出: 1

提示:

• n == s.length
• 1 <= n <= 200
• s[i] 不是 'I' 就是 'D'

分析

• 考虑最后一个数选 x
  • 假如 s[-1] 为 ‘D’，问题转为求剩下 n 个数的排列，最后一个数必须 >x
  • 求 [0,x-1]U[x+1,n] 的排列很麻烦，考虑将其映射为 [0,n-1] 的排列，即 >x 的数都减 1
  • 问题转为求 [0,n-1] 的排列，最后一个数>=x
  • 这就符合 dp 的结构了
  • s[-1] 为 ‘I’ 同理
• 于是令 f[i][j] 代表 [0,i] 的排列，且最后一个数选 j 的数量，有递推式
  • 若 s[i-1] 为 ‘D’，f[i][j] = sum(f[i-1][k] for k in range(j,i))
  • 若 s[i-1] 为 ‘I’， f[i][j] = sum(f[i-1][k] for k in range(j))
• 递推式显然可以用前缀和优化

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        mod = 10**9+7
        f = [1]
        for c in s:
            if c=='I':
                f = list(accumulate([0]+f))
            else:
                f = list(accumulate([0]+f[::-1]))[::-1]
            f = [a%mod for a in f]
        return sum(f)%mod

7 ms