LeetCode 1553. Minimum Number of Days to Eat N Oranges
LeetCode 1553. Minimum Number of Days to Eat N Oranges
ShenduCC
发布于 2020-09-17 11:15:14
发布于 2020-09-17 11:15:14
题意：一堆橘子，要么吃一个，如果橘子数量能被2整除就可以吃一半，如果橘子数量能被3整除就可以吃三分之二，请问最少几次能吃完？
题解：橘子的个数是n，按照贪心的思想，肯定是吃一半或者吃三分之二划算。因此每一步，都有两种选择，要么一个一给吃，吃到能被2整除，然后吃掉一半。要么一个一个吃，吃到能被3整除，然后吃掉三分之二。取二者的最小者。 所以，就是一个递归DP的过程，还要记得记录状态，以节约时间。
class Solution {
public:
map<int,int> dp;
int minDays(int n)
{
if (n <= 2)
return n;
if(dp[n]==0)
{
dp[n]= 1 + min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3));
}
return dp[n];
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-09-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读