通过备忘录来防止动态规划超时

吃掉n个橘子的最少天数

直接使用动态规划

dp[i]表示吃掉i个橘子所需要的最少天数。

• 可以先花一天吃1个，剩余 i-1个橘子，dp[i] = dp[i-1] + 1;
• 可以先花一天吃i / 2个，剩余i / 2个橘子， dp[i] = dp[i/2] + 1;
• 可以先花一天吃 2i / 3个，剩余i / 3个橘子，dp[i] = dp[i/3] + 1;

dp[1] = 1;
dp[2] = 2;
for(i = 3; 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];

这样有很多重复的子问题计算，是会超时的。

使用动态规划的递归 + 备忘录方法进行剪枝计算

我们肯定是先多次吃掉一个，然后达到n能被2整除或者是能被3整除的结果。
因此，我们能 选择1同选择2 或者 选择1同选择3。

• 1 + dp[n / 2] + n % 2
• 1 + dp[n / 3] + n % 3

class Solution {
    //吃掉n个需要多少天   备忘录
    HashMap<Integer, Integer> map = new HashMap<>();
    public int minDays(int n) {
        if(n <= 1) return n;
        //有记录的话直接返回
        if(map.containsKey(n)){
            return map.get(n);
        }
        //比较 递归    
        int min = Math.min(n % 2 + 1 + minDays(n / 2), n % 3 + 1 + minDays(n / 3));
        //记录
        map.put(n, min);
        return min;
    }
}

BFS

每天都有三种选择，相当于一棵树，根节点是N个橘子，子节点是当天选择取多少橘子剩余的橘子，先从选择3开始，因为要保证尽量花最少的天数。
借助HashSet<Integer> visited去标记一些已经拿过的橘子数。

class Solution {
    public int minDays(int n) {
            HashSet<Integer> visited = new HashSet<>();
            LinkedList<Integer> queue = new LinkedList<>();
            queue.add(n);
            int level = 0;
            while(!queue.isEmpty()){
                level ++;
                int size = queue.size();
                for(int i = 0; i < size; i++){
                    int poll = queue.poll();

                    if(poll >= 3 && poll % 3 == 0){
                        helper(queue, poll / 3, visited);
                    }

                    if(poll >= 2 && poll % 2 == 0){
                        helper(queue, poll / 2, visited);
                    }
                    if(poll > 1){
                        helper(queue, poll - 1, visited);
                    }else{
                        return level;
                    }
                }
            }
            return -1;
    }

    public void helper(LinkedList<Integer> queue, int poll, HashSet<Integer> visited){
        if(!visited.contains(poll)){
            queue.add(poll);
            visited.add(poll);
        }
    }
}