作者推荐
本文涉及知识点
动态规划汇总 数学
力扣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
动态规划
dp[i][j] 表示i只小猪，j回合能发现buckets 桶液体中的毒药。
一只小猪
一回合小猪只能喝一桶，如果同时喝两桶，结果没出来，猪没了。也就是极端情况下：一回合排除一桶。
dp[1][j] = j+1 注意 j为0时，也是符合的。
两只小猪
| 一回合 | 第一桶药，两头小猪喝；第二桶药，第一头小猪喝；第三桶药，第二头只小猪喝；第四桶药不喂给小猪。如果两只小猪都死了，第一桶药有毒；如果第一头小猪死了，第二桶有毒；如果第二头小猪死了，第三桶有毒；两只小猪都没死，第四桶有毒。===>>> dp[2][1] = 4 |
| 二回合 | 两头小猪都喂，如果有毒，小猪变成0只，dp[0][1] ; 只喂第一头小猪，如果有毒，猪变成一头 dp[1][1];同理，只喂第二头小猪类似：dp[1][1];不喂任何小猪的液体，两头猪：dp[2][1]。故结果为：dp[0][1] + dp[1][1]+dp[2][1] = 1 + 2 + 2 +4 |
总结i头猪j回合
| 喂所有猪的液体 | dp[0][j-1] |
| 喂i-1头猪的液体 | C i i − 1 ^{i-1}_{i}ii−1 *dp[1][j-1] |
| 喂i-2头猪的液体 | Ci i − 2 ^{i-2}_iii−2*dp[2][j-1] |
| … | |
| 喂1头猪的液体 | Ci 1 ^1_ii1*dp[i-1][j-1] |
| 喂0头猪的液体 | Ci 0 ^0_ii0*dp[i][j-1] |
喂k头猪液体的最大数量为：Ci k ^k_iik*dp[i-k][j-1]
故dp[i][j] = Sum[ 0 , i ] k ^k_{[0,i]}[0,i]kCi k ^k_iik*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; } };
测试用例
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); } }
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;
}
};
