【动态规划 数学归纳法 二项式定理】C++ 算法458:可怜的小猪_动态规划 归纳法

作者推荐

视频算法专题

本文涉及知识点

数学归纳法 二项式定理

动态规划汇总 数学

力扣458:可怜的小猪

有 buckets 桶液体，其中 正好有一桶 含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回 在规定时间内判断哪个桶有毒所需的 最小 猪数 。
示例 1：
输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出：5
示例 2：
输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
输出：2
示例 3：
输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
输出：2
提示：
1 <= buckets <= 1000
1 <= minutesToDie <= minutesToTest <= 100

2024年4月25总结

动态规划

dp[t][n]表示n只小猪 t回合能排除多少桶。
n只小猪有2ⁿ种死亡组合。mask$\in$[0,2ⁿ) ，i$\in$[0,n), 最低位为第0位。第mask种组合的第i位为1,表示第i只小猪死亡；为0，表示第0只小猪存活。只有一回合时，第种组合只能有一桶。故：dp[1][n] = 2ⁿ。 特例n为0，也成立
从小到大处理t，可以保证无后效性。
第t回合，如果mask 会死n1只小猪，则会存活n-n1只小猪。这种组合，喂dp[t-1][n-n1]桶。

数学归纳法

结论；dp[t][n] = (t+1)ⁿ
t等于1时：dp[1][n] = (t+1)ⁿ= 2ⁿ 得证。
令t=m时，结论正确。则t = m+1是，也正确。
$$\begin{gathered} dp[m+1][n]=\left(\genfrac{}{}{0ex}{}{n}{0}\right)dp[m][n]+\left(\genfrac{}{}{0ex}{}{n}{1}\right)dp[m][n-1]\cdots \left(\genfrac{}{}{0ex}{}{n}{n}\right)dp[m][0] \\ =\left(\genfrac{}{}{0ex}{}{n}{0}\right)(m+1{)}^n+(\genfrac{}{}{0ex}{}{n}{1})(m+1{)}^n-1\cdots \left(\genfrac{}{}{0ex}{}{n}{n}\right)(m+1{)}^0根据假设 \\ =(1+m+1{)}^n根据二相式定理 \\ =((m+1)+1{)}^n得证 \end{gathered}$$

动态规划

dp[i][j] 表示i只小猪，j回合能发现buckets 桶液体中的毒药。

一只小猪

一回合小猪只能喝一桶，如果同时喝两桶，结果没出来，猪没了。也就是极端情况下：一回合排除一桶。
dp[1][j] = j+1 注意 j为0时，也是符合的。

两只小猪

总结i头猪j回合

喂k头猪液体的最大数量为：C${}_i^k$*dp[i-k][j-1]
故dp[i][j] = Sum${}_{[0,i]}^k$C${}_i^k$*dp[i-k][j-1]
空间复杂度： O(mn) m是回合数，不超过100，n是小猪数，不超过1000。
计算一种状态的时间复杂度是：O(n)
故总的时间复杂度 是O(nnm)，这是理论值。刚刚超时，实际上不会。
当m等于1时，n=10。 就算1000桶，一回合，也只要10只小猪。所以n的最大值是10，不是1000。

代码

核心代码

class CCombination
{
public:
	CCombination( )
	{
		m_v.assign(1,vector<int>());		
	}
	int Get(int sel, int total)
	{
		while (m_v.size() <= total)
		{
			int iSize = m_v.size();
			m_v.emplace_back(iSize + 1, 1);
			for (int i = 1; i < iSize; i++)
			{
				m_v[iSize][i] = m_v[iSize - 1][i] + m_v[iSize - 1][i-1];
			}
		}
		return m_v[total][sel];
	}
protected:
	vector<vector<int>> m_v;	
};
class Solution {
public:
	int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
		const int iTurn = minutesToTest / minutesToDie;
		CCombination com;
		vector<vector<int>> dp(1,vector<int>(iTurn+1,1));
		while (dp.back().back() < buckets)
		{
			const int iPigNum = dp.size();
			dp.emplace_back(iTurn + 1, 1);
			auto& v = dp.back();
			for (int i = 1; i <= iTurn; i++)
			{
				v[i] = 0;
				for (int k = 0; k <= iPigNum; k++)
				{
					v[i] += com.Get(k,iPigNum) * dp[iPigNum - k][i - 1];
				}
			}
		}
		return dp.size() - 1;
	}
};
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

测试用例

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 buckets = 1000, minutesToDie = 15, minutesToTest;
	{
		Solution sln;
		buckets = 1000, minutesToDie = 15, minutesToTest = 60;
		auto res = sln.poorPigs(buckets, minutesToDie, minutesToTest);
		Assert(5, res);
	}
	{
		Solution sln;
		buckets = 4, minutesToDie = 15, minutesToTest = 15;
		auto res = sln.poorPigs(buckets, minutesToDie, minutesToTest);
		Assert(2, res);
	}
	{
		Solution sln;
		buckets = 4, minutesToDie = 15, minutesToTest = 30;
		auto res = sln.poorPigs(buckets, minutesToDie, minutesToTest);
		Assert(2, res);
	}


}
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

2023年1月版

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
vector p;
p.push_back(1);
for (int i = 1; i <= 10; i++)
{
p.push_back(i*p[i - 1]);
}
vector<vector> dp;
dp.assign(11, vector(minutesToTest / minutesToDie + 1,1));
if (buckets <= 1)
{
return 0;
}
for (int i = 1; i <= 10; i++)
{
for (int j = 1; j <= minutesToTest / minutesToDie; j++)
{
int iSum = 0;
for (int k = 0; k <= i; k++)
{
iSum += dp[k][j - 1] * (p[i] / p[k] / p[i - k]);
}
dp[i][j] = iSum;
}
if (dp[i].back() >= buckets)
{
return i;
}
}
return 10;
}
};

2023年6月版

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
const int iMaxTestNum = minutesToTest / minutesToDie;
//10只猪一轮，可以搞定1024 桶。所以10只猪够用了
const int iMaxPig = 10;
vector<vector> vCom(iMaxPig + 1, vector(iMaxPig + 1, 1));//组合
{
for (int i = 1; i <= iMaxPig; i++)
{
for (int j = 1; j < i; j++)
{//从i个小猪中选择j个的可能
vCom[i][j] = vCom[i - 1][j - 1] + vCom[i-1][j];
}
}
}
vector<vector> dp(iMaxTestNum + 1, vector(iMaxPig + 1, 1));
for (int i = 1; i <= iMaxTestNum; i++)
{
for (int j = 1; j <= iMaxPig; j++)
{
int iSum = 0;
for (int k = 0; k <= j; k++)
{
iSum += vCom[j][k] * dp[i - 1][j - k];
}
dp[i][j] = iSum;
}
}
for (int i = 0; i <= iMaxPig; i++)
{
if (dp[iMaxTestNum][i] >= buckets)
{
return i;
}
}
return -1;
}
};

2023年8月版

class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int iStep = minutesToTest / minutesToDie;
int iCanFindBucket = 1;
for (int pig = 0; ; pig++)
{
if (iCanFindBucket >= buckets)
{
return pig;
}
iCanFindBucket *= (iStep + 1);
}
return 0;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。