作者推荐
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
涉及知识点
记忆化搜索 剪枝 分类讨论
LeetCode1553. 吃掉 N 个橘子的最少天数
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
示例 1：
输入：n = 10
输出：4
解释：你总共有 10 个橘子。
第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。
示例 2：
输入：n = 6
输出：3
解释：你总共有 6 个橘子。
第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。
示例 3：
输入：n = 1
输出：1
示例 4：
输入：n = 56
输出：6
提示：
1 <= n <= 2*109
分类讨论
具有如下性质：
性质一：如果n>=3，则不可能全部是方案一，必定有方案二或方案三。当只有三个桔子时，采用方案三，只需要2天；全部全部使用方案一，则需要3天。
性质二：如 n>=4 ，且没有使用方案三或先使用方案二。则必定在n/22处采用方案二。反证法：假定某一方案，在j2个桔子时，首先使用方案二,j < n/2 假定一 。 n → \rightarrow→n/22 和j→ \rightarrow→ 0完全一样，所以只讨论：n/22 → \rightarrow→ j。
n/2 ⋆ \star⋆ 2 → \rightarrow→ n/2 → \rightarrow→ j ，最多用了:1+ (n/2) - j 天。式子一
n/2 ⋆ \star⋆ 2 → \rightarrow→ 2j → \rightarrow→ j 用了 n-2j+1 = n/2-j+ 1+(n/2)-j 式子二
式子二减去式子一：n/2- j 根据假定一，大于0。故：必定在n/22处采用方案二。
性质三：如果n >=6。且没有使用方案二或先使用方案三，则必定n/3*3出采用方案三。证明类似。
代码
核心代码
class Solution { public: int minDays(int n) { m_data[1] = 1; m_data[2] = 2; m_data[3] = 2; return Rec(n); } int Rec(int n) { if (m_data.count(n)) { return m_data[n]; } return m_data[n] = min(Rec(n / 2 ) +n %2 +1 , Rec(n / 3)+ 1 + n %3 ); } unordered_map<int, int> m_data; };
测试用例
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() { { Solution sln; vector<int> in = { 1,2,3,4,5,6,10,2000000000 }; vector<int> ans = { 1,2,2,3,4,3 ,4,32}; vector<int> res(in.size()); for (int i = 0; i < in.size(); i++) { res[i] = sln.minDays(in[i]); } Assert(res, ans); } }
2023年2月
class Solution {
public:
int minDays(int n) {
if( n < 3 )
{
return n ;
}
return min( n%3 + minDays(n/3) +1 ,n%2 + minDays(n/2)+1);
}
};
2023年2月 第二版
class Solution {
public:
int minDays(int n) {
if( n < 3 )
{
return n ;
}
auto it = m_mNValue.find(n);
if( m_mNValue.end() !=it )
{
return it->second;
}
return m_mNValue[n] = min( n%3 + minDays(n/3) +1 ,n%2 + minDays(n/2)+1);
}
std::unordered_map<int,int> m_mNValue;
};
2023年7月
class Solution {
public:
int minDays(int n)
{
if (n < 3)
{
return n;
}
if (m_result.count(n))
{
return m_result[n];
}
int iRet3 = (0 == n % 3) ? (minDays(n / 3) + 1) : (minDays(n / 3 * 3) + n % 3);
int iRet2 = (0 == n % 2) ? (minDays(n / 2) + 1) : (minDays(n / 2 * 2) + n % 2);
return m_result[n] = min(iRet3, iRet2);
}
std::unordered_map<int, int> m_result;
};
2023年9月
class Solution {
public:
int minDays(int n) {
if (n < 3)
{
return n;
}
if (m_mRes.count(n))
{
return m_mRes[n];
}
int iRet = min(minDays(n / 3) + 1 + n % 3, minDays(n / 2) + 1 + n % 2);
return m_mRes[n] = iRet;
}
std::unordered_map<int, int> m_mRes;
};
