5490. 吃掉 N 个橘子的最少天数

太过爱你忘了你带给我的痛 2022-11-27 15:56 55阅读 0赞

## 问题描述： ##

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

吃掉一个橘子。  
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。  
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2\*(n/3) 个橘子。  
每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/minimum-number-of-days-to-eat-n-oranges][https_leetcode-cn.com_problems_minimum-number-of-days-to-eat-n-oranges]

**提示：**

*  `1 <= n <= 2*10^9`

## 解题思路： ##

动态规划

class Solution {
        public int minDays(int n) {
            if(n==0 || n==1 ||n==2) return n;
            int[] dp = new int[n+1];
            dp[1] = 1;
            dp[2] = 2;
            for(int i=3;i<=n;i++){
                dp[i] = Math.min(dp[i-1]+1,dp[i]);
                if(i%2==0)  dp[i] = Math.min(dp[i/2]+1,dp[i]);
                if(i%3==0)  dp[i] = Math.min(dp[i/3]+1,dp[i]);
                
            }
            return dp[n];
        }
    }

但是这里时间和空间都会超出内存

## 记忆化搜索 ##

class Solution {
        Map<Integer,Integer> dp = new HashMap<>();
        public int minDays(int n) {
            dp.put(0,0);
            dp.put(1,1);
            dp.put(2,2);
            if(dp.containsKey(n)) return dp.get(n);
            int res = Math.min(minDays(n/2)+n%2+1,minDays(n/3)+n%3+1);
            dp.put(n,res);
            return dp.get(n);
        }
    }

[https_leetcode-cn.com_problems_minimum-number-of-days-to-eat-n-oranges]: https://leetcode-cn.com/problems/minimum-number-of-days-to-eat-n-oranges