LeetCode 920. 播放列表的数量

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 920. 播放列表的数量

思路分析

解法一：动态规划（推荐）

核心思路：

定义 dp[i][j] 为恰好听了 i 首歌且列表中包含 j 首不同歌曲的播放列表数量

转移方程分两种情况：新加一首从未听过的歌 dp[i][j] += dp[i-1][j-1] * (n - (j-1))；重复一首之前听过的歌，但不是最近 k 首，dp[i][j] += dp[i-1][j] * max(0, j - k)

初始状态 dp[0][0] = 1，最终答案为 dp[goal][n]

使用滚动数组将空间优化至 O(n)

复杂度分析：

时间复杂度：O(goal × n)，其中 goal 为播放列表长度，n 为歌曲总数

空间复杂度：O(n)，滚动数组只保留一行状态

class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        long mod = 1_000_000_007L;

        // dp[j] 表示当前播放列表中恰好包含 j 首不同歌曲的方案数
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= goal; i++) {
            // 从后向前遍历，避免覆盖
            long[] newDp = new long[n + 1];

            for (int j = 1; j <= Math.min(i, n); j++) {
                // 情况一：第 i 首是新歌，从 n-(j-1) 首中选
                newDp[j] = (newDp[j] + dp[j - 1] * (n - (j - 1))) % mod;

                // 情况二：第 i 首是旧歌，但不在最近 k 首中
                if (j > k) {
                    newDp[j] = (newDp[j] + dp[j] * (j - k)) % mod;
                }
            }

            dp = newDp;
        }

        return (int) dp[n];
    }
}

func numMusicPlaylists(n int, goal int, k int) int {
    const mod = 1_000_000_007

    // dp[j] 表示播放列表中恰好包含 j 首不同歌曲的方案数
    dp := make([]int, n+1)
    dp[0] = 1

    for i := 1; i <= goal; i++ {
        newDp := make([]int, n+1)

        for j := 1; j <= min920(i, n); j++ {
            // 情况一：第 i 首是新歌，从 n-(j-1) 首未播放过的歌中选
            newDp[j] = (newDp[j] + dp[j-1]*(n-(j-1))) % mod

            // 情况二：第 i 首是旧歌，但不在最近 k 首中
            if j > k {
                newDp[j] = (newDp[j] + dp[j]*(j-k)) % mod
            }
        }

        dp = newDp
    }

    return dp[n]
}

func min920(a, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
518. 零钱兑换 II	中等	动态规划、组合计数
377. 组合总和 Ⅳ	中等	动态规划、排列计数
1359. 有效的快递序列数目	困难	动态规划、数学
62. 不同路径	中等	动态规划、组合数学
96. 不同的二叉搜索树	中等	动态规划、卡特兰数
1866. 恰好有 K 根木棍可以看到的排列数目	困难	动态规划、第一类斯特林数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/58820621