Hard

题目描述

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

  • ‘D’ 表示递减，或
  • ‘I’ 表示递增。

一个由范围 [0, n] 内所有整数组成的 n + 1 个整数的排列 perm 被称为有效排列，如果对于所有有效的 i：

  • 如果 s[i] == ‘D’，那么 perm[i] > perm[i + 1]，并且
  • 如果 s[i] == ‘I’，那么 perm[i] < perm[i + 1]。

返回有效排列 perm 的数量。由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：s = "DID"
输出：5
解释：(0, 1, 2, 3) 的 5 个有效排列是：
(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’。

解题思路

这是一个经典的动态规划问题，关键在于理解排列的相对大小关系。

核心观察： 对于任意有效排列，我们只关心数字之间的相对大小关系，而不是具体的数值。因此可以考虑使用相对排名来简化问题。

状态定义： 设 dp[i][j] 表示考虑前 i+1 个位置，且第 i 个位置上的数字在这 i+1 个数字中排名第 j（从小到大，0-indexed）的方案数。

状态转移：

  1. 如果 s[i-1] == 'D'（递减）：当前位置的数字应该比下一个位置大。在相对排名中，如果当前位置排名为 j，那么下一个位置的排名应该在 [0, j] 范围内。
  2. 如果 s[i-1] == 'I'（递增）：当前位置的数字应该比下一个位置小。在相对排名中，如果当前位置排名为 j，那么下一个位置的排名应该在 [j, i] 范围内（注意新加入一个数字后排名会发生变化）。

优化： 使用前缀和优化状态转移，避免重复计算。

时间复杂度为 O(n²)，空间复杂度可以优化到 O(n)。

代码实现

class Solution {
public:
    int numPermsDISequence(string s) {
        int n = s.length();
        const int MOD = 1e9 + 7;
        
        vector<long long> dp(n + 2, 1);
        
        for (int i = 0; i < n; i++) {
            vector<long long> new_dp(n + 2, 0);
            long long cumsum = 0;
            
            if (s[i] == 'D') {
                for (int j = i; j >= 0; j--) {
                    cumsum = (cumsum + dp[j]) % MOD;
                    new_dp[j] = cumsum;
                }
            } else {
                for (int j = 0; j <= i; j++) {
                    cumsum = (cumsum + dp[j]) % MOD;
                    new_dp[j] = cumsum;
                }
            }
            dp = new_dp;
        }
        
        long long result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[j]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numPermsDISequence(self, s: str) -> int:
        n = len(s)
        MOD = 10**9 + 7
        
        dp = [1] * (n + 2)
        
        for i in range(n):
            new_dp = [0] * (n + 2)
            cumsum = 0
            
            if s[i] == 'D':
                for j in range(i, -1, -1):
                    cumsum = (cumsum + dp[j]) % MOD
                    new_dp[j] = cumsum
            else:
                for j in range(i + 1):
                    cumsum = (cumsum + dp[j]) % MOD
                    new_dp[j] = cumsum
            
            dp = new_dp
        
        return sum(dp) % MOD

public class Solution {
    public int NumPermsDISequence(string s) {
        int n = s.Length;
        const int MOD = 1000000007;
        
        long[] dp = new long[n + 2];
        for (int i = 0; i < n + 2; i++) {
            dp[i] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            long[] newDp = new long[n + 2];
            long cumsum = 0;
            
            if (s[i] == 'D') {
                for (int j = i; j >= 0; j--) {
                    cumsum = (cumsum + dp[j]) % MOD;
                    newDp[j] = cumsum;
                }
            } else {
                for (int j = 0; j <= i; j++) {
                    cumsum = (cumsum + dp[j]) % MOD;
                    newDp[j] = cumsum;
                }
            }
            dp = newDp;
        }
        
        long result = 0;
        for (int j = 0; j <= n; j++) {
            result = (result + dp[j]) % MOD;
        }
        
        return (int)result;
    }
}

var numPermsDISequence = function(s) {
    const n = s.length;
    const MOD = 1e9 + 7;
    
    let dp = new Array(n + 2).fill(1);
    
    for (let i = 0; i < n; i++) {
        let newDp = new Array(n + 2).fill(0);
        let cumsum = 0;
        
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环遍历所有状态
空间复杂度O(n)使用一维数组存储状态