Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

👨‍💻 Алгоритм:

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j.

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

class Solution {
    func numPermsDISequence(_ s: String) -> Int {
        let MOD = 1_000_000_007
        let n = s.count
        var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
        dp[0][0] = 1
        
        let sArray = Array(s)
        for i in 1...n {
            for j in 0...i {
                if sArray[i - 1] == "D" {
                    dp[i][j] = (j..<i).reduce(0) { ($0 + dp[i - 1][$1]) % MOD }
                } else {
                    dp[i][j] = (0..<j).reduce(0) { ($0 + dp[i - 1][$1]) % MOD }
                }
            }
        }
        
        return dp[n].reduce(0) { ($0 + $1) % MOD }
    }
}

Ставь 👍 и забирай 📚 Базу знаний