发表于 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找到结果，但还是没想出来。

• LC 题目链接