Задача: 920. Number of Music Playlists4
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

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

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

function numMusicPlaylists($n, $goal, $k) {
    $MOD = 1_000_000_007;
    $dp = array_fill(0, $goal + 1, array_fill(0, $n + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $goal; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            $dp[$i][$j] = $dp[$i-1][$j-1] * ($n - $j + 1) % $MOD;
            if ($j > $k) {
                $dp[$i][$j] = ($dp[$i][$j] + $dp[$i-1][$j] * ($j - $k) % $MOD) % $MOD;
            }
        }
    }

    return $dp[$goal][$n];
}

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