920. Number of Music Playlists

LeetCode hard original: C# #array #csharp #dynamic-programming #hard #leetcode

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

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

Exemplo:

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

Output: 6

C# solução

correspondente/original

public class Solution {
    public int NumMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1_000_000_007;
        long[,] dp = new long[goal + 1, n + 1];
        dp[0, 0] = 1;
        for (int i = 1; i <= goal; i++) {
            for (int 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 (int)dp[goal, n];
    }
}

C++ solução

rascunho automático, revisar antes de enviar

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1_000_000_007;
        long[,] dp = new long[goal + 1, n + 1];
        dp[0, 0] = 1;
        for (int i = 1; i <= goal; i++) {
            for (int 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 (int)dp[goal, n];
    }
}

Java solução

correspondente/original

class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        final int MOD = 1_000_000_007;
        long[][] dp = new long[goal + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int 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 (int) dp[goal][n];
    }
}

JavaScript solução

correspondente/original

var numMusicPlaylists = function(n, goal, k) {
    const MOD = 10**9 + 7;
    let dp = Array.from({ length: goal + 1 }, () => Array(n + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= goal; i++) {
        for (let 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];
};

Python solução

correspondente/original

def numMusicPlaylists(n, goal, k):
    MOD = 10**9 + 7
    dp = [[0] * (n + 1) for _ in range(goal + 1)]
    dp[0][0] = 1

    for i in range(1, goal + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
            if j > k:
                dp[i][j] += dp[i-1][j] * (j - k) % MOD
            dp[i][j] %= MOD

    return dp[goal][n]

Go solução

correspondente/original

package main

func numMusicPlaylists(n int, goal int, k int) int {
    const MOD = 1_000_000_007
    dp := make([][]int, goal+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    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]
}

Algorithm

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

Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.

Заполнить array dp, используя два случая:

Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)

Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

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

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.