2024-5-12——吃掉 N 个橘子的最少天数

本文主要是介绍2024-5-12——吃掉 N 个橘子的最少天数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024-5-12

- - 题目来源
  - 我的题解
  - - 方法一深度搜索超时
    - 方法二动态规划超内存
    - 方法三灵神题解

题目来源

力扣每日一题；题序：1553

我的题解

方法一深度搜索超时

直接使用深度搜索，每次选择一种策略，然后判断最小值

class Solution {int res=Integer.MAX_VALUE;public int minDays(int n) {dfs(n,0);return res;}public void dfs(int n,int day){if(n<=0){if(n==0)res=Math.min(day,res);return ;}for(int i=0;i<3;i++){if(i==0)dfs(n-1,day+1);else if(i==1&&n%2==0)dfs(n-n/2,day+1);else if(i==2&&n%3==0)dfs(n-2*(n/3),day+1);}}
}

//使用记忆化搜索优化
class Solution {int res=Integer.MAX_VALUE;public int minDays(int n) {int[][] memo=new int[n+1][n+1];for(int[] t:memo)Arrays.fill(t,-1);dfs(n,0,memo);return res;}public int dfs(int n,int day,int[][] memo){if(n<=0){if(n==0)res=Math.min(day,res);return 0;}if(memo[n][day]!=-1){return memo[n][day];}int ans=Integer.MAX_VALUE;for(int i=0;i<3;i++){if(i==0)ans=Math.min(dfs(n-1,day+1,memo),ans);else if(i==1&&n%2==0)ans=Math.min(dfs(n-n/2,day+1,memo),ans);else if(i==2&&n%3==0)ans=Math.min(dfs(n-2*(n/3),day+1,memo),ans);}memo[n][day]=ans;return ans;}
}

方法二动态规划超内存

dp[i]=min(dp[i-1],dp[i/2],dp[i/3])+1;

时间复杂度：O(n)
空间复杂度：O(n)

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

方法三灵神题解

参考灵神题解

class Solution {private final Map<Integer, Integer> memo = new HashMap<>();public int minDays(int n) {if (n <= 1) {return n;}Integer res = memo.get(n);if (res != null) { // 之前计算过return res;}res = Math.min(minDays(n / 2) + n % 2, minDays(n / 3) + n % 3) + 1;memo.put(n, res); // 记忆化return res;}
}