920.md

920 Number of Music Playlists

Description

link

---

Solution

• See Code

---

Code

Complexity T : O((L-K)(N-K)) M : O((N)(L))

class Solution:
    """
    F(N,L,K) = F(N - 1, L - 1, K) * N + F(N, L - 1, K) * (N - K)
    
    F(N, L - 1, K)
    If already N in the L - 1 first songs.
    We can put any song at the end of music list,
    but it should be different from K last song.
    We have N - K choices.
    """
    def numMusicPlaylists(self, N: int, L: int, K: int) -> int:
        # O((L-K)(N-K))
        dp = [[0 for i in range(L + 1)] for j in range(N + 1)]
        for i in range(K + 1, N + 1): # i 代表N的可取值循环 从K+1开始，因为N少于K无效，注意此时的默认k为K
            for j in range(i, L + 1): # j 代表L的可取值循环 从i开始，因为L小于当前i可以直接算出来
                if i == j or i == K + 1: # 初始化的时候，直接算出i的阶乘即可，比如【3，3，K】或者 【K+1，j，K】
                    dp[i][j] = math.factorial(i)
                else:
                    dp[i][j] = dp[i - 1][j - 1] * i + dp[i][j - 1] * (i - K)
        return dp[N][L] % (10**9 + 7)