JZX轻语：简
LeetCode 1553 - 吃掉N个橘子的最少天数
发表于2024年05月12日
一个需要亿点证明的动态规划/记忆化搜索题目，朴素的状态转移方案为minDays(n) = 1 + min(minDays(n - 1), minDays(n // 2) if n % 2 == 0, minDays(n // 3) if n % 3 == 0)。但这样，对于特别大的n，不断-1很容易爆栈。因此，可以根据证明得到，每次-1的操作都是有限的，在每次递归中我们只要减到能被2或者3整除就行。
一开始的做法：
import math
class Solution:
def __init__(self):
self.buffer = {}
def minDays(self, n: int) -> int:
if n in self.buffer:
return self.buffer[n]
if n == 1 or n == 0:
return n
ans = math.inf
if not n % 2:
ans = min(ans, self.minDays(n // 2) + 1)
else:
ans = min(ans, self.minDays(n - 1) + 1)
if not n % 3:
ans = min(ans, self.minDays(n // 3) + 1)
else:
r = n % 3
ans = min(ans, self.minDays(n - r) + r)
self.buffer[n] = ans
return ans改进的做法：
import functools
class Solution:
@functools.lru_cache(None)
def minDays(self, n: int) -> int:
if n == 1 or n == 0:
return n
return min(
n % 2 + 1 + self.minDays(n // 2),
n % 3 + 1 + self.minDays(n // 3)
)官方题解的最短路/启发式搜索也比较有意思。一开始也想到使用队列类似的做法，BFS找到结果，但还是没想出来。