Задача: 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.

😎 Решение:

function numPermsDISequence($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, array_fill(0, $n + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j <= $i; $j++) {
            if ($s[$i - 1] == 'D') {
                for ($k = $j; $k < $i; $k++) {
                    $dp[$i][$j] = ($dp[$i][$j] + $dp[$i - 1][$k]) % $MOD;
                }
            } else {
                for ($k = 0; $k < $j; $k++) {
                    $dp[$i][$j] = ($dp[$i][$j] + $dp[$i - 1][$k]) % $MOD;
                }
            }
        }
    }

    $result = 0;
    for ($j = 0; $j <= $n; $j++) {
        $result = ($result + $dp[$n][$j]) % $MOD;
    }

    return $result;
}

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