【动态规划】【组合数学】【C++算法】920播放列表的数量

本题同解

【放球问题】920. 播放列表的数量

本文涉及知识点

动态规划汇总
组合数学

LeetCode920播放列表的数量

你的音乐播放器里有 n 首不同的歌，在旅途中，你计划听 goal 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：
每首歌 至少播放一次 。
一首歌只有在其他 k 首歌播放完之后才能再次播放。
给你 n、goal 和 k ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 109 + 7 取余 的结果。
示例 1：
输入：n = 3, goal = 3, k = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] 。
示例 2：
输入：n = 2, goal = 3, k = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2] 。
示例 3：
输入：n = 2, goal = 3, k = 1
输出：2
解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2] 。
提示：
0 <= k < n <= goal <= 100

动态规划+组合数学

*条件一：一首歌只有在其他 k 首歌播放完之后才能再次播放。换种说法：相同的歌曲之间至少有其它k首歌。令某个播放列表的歌曲分别为：
a[0] a[1] …a[goal-1]。 对于a的任意下标i,j, i < j，如果 a[i] == a[j]，那么 区间(j,j) 至少k个数 → \rightarrow → j-i-1 >=k → \rightarrow → j-i >= k+1 → \rightarrow → 除了前面k个数，其它数都可以选择。下标j 可以选择的数如下：
D ( x ) = { n − k j > = k n − j , j < k D(x) = {n−kj>=kn−j,j<k

{n−kn−j,j>=kj<k
D(x)={n−kn−j,​j>=kj<k​
可以简化成n - min(j,k)
*条件二：每首歌必须听一次。数组a的元素，如果是第一次出现，保留，其它删除。删除后，就是b。比如：{1,2,1,3} → \rightarrow → {1,2,3}
我们先假定b是升序，计算出结果后再乘以b的排列数 P n n P\Large_n^n Pnn​。

动态规划的状态表示

pre[i]表示前j首歌，已经选择了i个不同歌曲的播放列表数量。dp[i]表示前j+1首歌，已经选择了i个不同歌曲的播放列表数量。
状态数： n × \times × goal

动态规划的转移方程

b表示包括j未听的歌大于未选择的歌曲数。b==true，可以选择旧歌曲;!b，必须选择新歌曲。b=(goal-j) > (n-i)。
通过pre[j]更新dp的方程如下：
D ( x ) = { 听旧歌 d p [ i ] + = p r e [ i ] ∗ ( i − m i n ( j , k ) ) b 听新歌 d p [ i + 1 ] + = p r e [ i ] i < n D(x) = {听旧歌dp[i]+=pre[i]∗(i−min(j,k))b听新歌dp[i+1]+=pre[i]i<n

D(x)={听旧歌dp[i]+=pre[i]∗(i−min(j,k))听新歌dp[i+1]+=pre[i]​bi<n​
转移方程的时间复杂度是O(1)，故总时间复杂度O( n × \times × goal)

动态规划的初始值

pre[0] = 1 ，其它为零。

动态规划的填表顺序

j从0到大。

动态规划的返回值

pre.back()

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};

class Solution {
public:
	int numMusicPlaylists(int n, int goal, int k) {
		vector<C1097Int<>> pre(n + 1);
		pre[0] = 1;
		for (int j = 0; j < goal; j++)
		{
			vector<C1097Int<>> dp(n + 1);
			for (int i = 0; i <= n; i++)
			{
				bool b = (goal - j) > (n - i);
				if (b)
				{
					dp[i] += pre[i] * (i - min(j, k));
				}
				if (i + 1 <= n)
				{
					dp[i + 1] += pre[i];
				}
			}
			pre.swap(dp);
		}		
		auto biRet = pre.back();
		for (int i = 1; i <= n; i++)
		{
			biRet *= i;
		}
		return biRet.ToInt();
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	int n = 3, goal = 3, k = 1;
	{
		Solution sln;
		n = 3, goal = 3, k = 1;
		auto res = sln.numMusicPlaylists(n, goal, k);
		Assert(res, 6);
	}
	{
		Solution sln;
		n = 2, goal = 3, k = 0;
		auto res = sln.numMusicPlaylists(n, goal, k);
		Assert(res, 6);
	}
	{
		Solution sln;
		n = 2, goal = 3, k = 1;
		auto res = sln.numMusicPlaylists(n, goal, k);
		Assert(res, 2);
	}
	

	


}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

2023年1月版

class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
vector preDP(1, 1);
int iMaxNum = 0;
while (goal–)
{
iMaxNum = min(n, iMaxNum+1 );
vector dp(iMaxNum + 1);
for (int i = 0; i < preDP.size(); i++ )
{
dp[i] += preDP[i] * max(0, i - k);
if (i + 1 < dp.size())
{
dp[i + 1] += preDP[i] * (n - i);
}
}
preDP.swap(dp);
}
return preDP[n].ToInt();
}
};

2023年8月版

class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
C1097Int<> biRet(1);
int i = 0;
int iSel = n;
for (; i < k; i++)
{
biRet *= iSel–;
}
const int iRemain = n - k;
vector< C1097Int<>> pre(iRemain + 1, 0);
pre[iRemain] = biRet;
for (; i < goal; i++)
{
vector< C1097Int<>> dp(iRemain + 1,0);
for (int remain = 0; remain <= iRemain; remain++)
{
if (remain > 0)
{//从未选择的数中选择一个
dp[remain-1] += pre[remain] * remain;
}
//从已经选择的数中选择
dp[remain] += pre[remain] * (n - k - remain);
}
dp.swap(pre);
}
return pre[0].ToInt();
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+

+17**
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览61211 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/135710702"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！