题目分析

这是第202周周赛的第四题，题目的意思也很简单，有一堆橘子，每天可以选择吃掉一个，当橘子个数为2的整数倍时，每天还可以选择吃掉一半，当橘子个数为3的整数倍时，每天还可以选择吃掉三分之二，求如何最快吃完这些橘子。

BFS

这道题目做法有很多，但是测试样例中，橘子的个数可以达到$2 \times 10^9$，这样就不能使用DP来做了。DP的思路非常清晰，dp[i] = min(dp[i - 1], dp[i // 2], dp[i // 3]) + 1，当然i需要是能整除2和3的，否则去掉对应的那一项即可，这里就不再论述。时间复杂度为O(n)。我们思考，因为吃掉一半或者三分之二的概率非常大，所以结果应该不会很大，所以我们可以使用广搜的方法进行求解。为了避免搜到重复的情况，我们建立一个字典保存当前已经搜到的情况。时间复杂度为O(log(n))，空间复杂度为O(log(n))。

from collections import deque


class Solution(object):
    def minDays(self, n):
        """
        :type n: int
        :rtype: int
        """
        dic = {n: 0}
        queue = deque([n])
        while 0 not in dic:
            current = queue.popleft()
            if current % 3 == 0 and current // 3 not in dic:
                dic[current // 3] = dic[current] + 1
                queue.append(current // 3)
            if current % 2 == 0 and current // 2 not in dic:
                dic[current // 2] = dic[current] + 1
                queue.append(current // 2)
            if current - 1 not in dic:
                dic[current - 1] = dic[current] + 1
                queue.append(current - 1)
        return dic[0]

贪心+DFS

DFS速度更快，但是更难以想到，需要一些数学的思路。
能整除，我们就不吃一个，这是DFS的核心。如果n个橘子经过了k次吃一个的操作后，出现了除以3的操作，因此可以说明n - k是3的倍数，那么当k大于3时，这一定不是最优解，因为可以吃k - 3次一个橘子，然后除以3，再吃一个橘子。举个例子，101个橘子，如果每天吃一个橘子，吃了5天，然后剩余96个橘子，然后第六条吃了64个橘子，花费6天，橘子数目变为32。我们可以有一种更快到达32的方法，吃2个橘子，剩余99个橘子，然后第三天吃66个橘子，第四天吃一个橘子，花费4天，橘子数目变为32。

n个橘子经过k次吃一个的操作后，出现了除以2的操作同理。

因此我们采用一种贪心的算法，能整除则整除，不能整除先吃1个或2个然后再整除。使用记忆化的DFS，可以进一步加快搜索。时间复杂度为O(log(n))，空间复杂度为O(log(n))。

from functools import lru_cache


class Solution(object):
    def minDays(self, n):
        """
        :type n: int
        :rtype: int
        """
        @lru_cache(None)
        def dfs(n):
            if n < 3:
                return n
            return min(dfs(n // 2) + n % 2, dfs(n // 3) + n % 3) + 1
        return dfs(n)

刷题总结

非常有趣的题目，我当时想到了使用BFS去求解，但是没有使用字典保存，导致时间复杂度过高。小伙伴们要吸取教训，记忆化是一个非常好的搜索方法，可以从指数级的时间复杂度变成线性复杂度，一定要掌握呀。