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

问题描述：

厨房里总共有 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

提示：

• 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 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);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！