算法题常用模版

排序

快速排序

912. 排序数组

def partition(nums: List[int], left: int, right: int) -> int:
    # 随机找一个 pivot，放到应该的位置上，返回 pivot 的位置
    k = random.randint(left, right)
    nums[left], nums[k] = nums[k], nums[left]
    pivot = nums[left]
    i, j = left+ 1, right
    while True:
        while i <= j and nums[i] < pivot:
            i += 1
        while i <= j and nums[j] > pivot:
            j -= 1
        if i >= j:
            break
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1

    nums[left], nums[j] = nums[j], nums[left]
    return j

def quick_sort(left: int, right: int):
    if left >= right:
        return
    pos = partition(nums, left, right)
    quick_sort(left, pos - 1)
    quick_sort(pos + 1, right)

# 使用
nums = [...]
quick_sort(0, len(nums) - 1)

经过一次 partition 后，pivot 被放到了它在最终升序数组中的正确位置，左侧元素都不大于它，右侧元素都不小于它。（但左侧右侧里都有可能出现等于它的）

• 平均/期望时间复杂度：$O(nlogn)$

• 最坏时间复杂度：$O(n^2)$

• 空间复杂度：递归栈平均$O(logn)$，最坏 $O(n)$

  最坏情况是每次都选到区间的最小/最大值，导致递归调用树变成链表：f(n)=f(n-1)+O(n)；期望情况是 f(n)=2(fn/2)+O(n)

三路快排

三路快排是对原始快排的优化，主要区别在于经过一次划分后，小于 pivot 的在左边，等于 pivot 在中间，大于 pivot 在右边。这样一次划分之后，相同元素都被放到了正确位置上。优化了对有大量重复数字的数组的快排。

def partition(nums: List[int], left: int, right: int) -> int:
    # 三路划分
    k = random.randint(left, right)
    pivot = nums[k]
    lt, i, gt = left, left, right
    while i <= gt:
        if nums[i] < pivot:
            nums[lt], nums[i] = nums[i], nums[lt]
            lt += 1
            i += 1
        elif nums[i] > pivot:
            nums[gt], nums[i] = nums[i], nums[gt]
            gt -= 1
        else:
            i += 1
    return lt, gt

def quick_sort(left: int, right: int):
    if left >= right:
        return
    lt, gt = self.partition(nums, left, right)
    quick_sort(left, lt - 1)
    quick_sort(gt + 1, right)
 
# 使用
nums = [...]
quick_sort(0, len(nums) - 1)

关于指针移动：

• 对于第一个分支：如果 lt < i，那么 nums[lt] 一定等于 pivot；否则 lt == i. 由此在第一个分支中，要么自己和自己换，要么换过来的数一定等于 pivot，这两种情况 i 都可以直接加一；

• 对于第二个分支：右边换过来的元素没被检查过，不确定大小，因此 i 不能加一，留给下一轮循环检查。

关于 partition 完成后：

• nums[:lt] < pivot, nums[lt:gt+1] == pivot, nums[gt+1:] > pivot

快速选择

由于 partition 函数能够在 $O(r-l+1)$ 的时间内确定某个随机 pivot 在当前区间中的最终位置。利用这一点，可以在无序数组中查找第 k 小或第 k 大的元素，而不必完整排序。

若查找第 k 小：

def quick_select(nums: list[int], k: int):
# 第 k 小的数在排序数组中的下标是 k-1
    l, r = 0, len(nums) - 1
    while True:
        pos = partition(nums, l, r)
        if pos == k - 1:
            return nums[pos]
        elif pos < k - 1:
            l = pos + 1
        else:
            r = pos - 1

若查找第 k 大，则目标下标应为 len(nums) - k。

快速选择的期望时间复杂度为 $O(n+\frac{n}{2}+\frac{n}{4}+...)\approx O(n)$ ，最坏时间复杂度为 $O(n^2)$。

链表

两个问题：

1. 什么时候需要设置一个 dummy 结点？

   当需要修改链表结构时基本都用 dummy

   当头结点可能会发生改变时，设置 dummy 结点。dummy 结点就是一个指向头结点的虚拟空节点，最大的作用就是不用去处理特判改变对象为头结点时的特殊情况。另外，如果题目要求返回头结点，可以方便地直接返回 dummy.next 。

2. 什么时候用 while cur，什么时候用 while cur.next ？

   当循环为 while cur 时，最后一次进入循环时 cur 位于尾结点，循环结束后 cur 为 None；

   当循环为 while cur.next 时，最后一次进入循环时 cur 位于倒数第二个结点，循环结束后 cur 为尾结点。

   具体题目我们只要想一想我们要让最后一次循环体发生时的边界是什么来判断即可。

单链表定义：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

反转链表

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

这是迭代写法，还有一种递归写法，但不实用。

快慢指针

• 快指针先走 n 步，慢指针再走

  19. 删除链表的倒数第 N 个结点

  删除操作需要找到被删除结点的前一个结点即可，因此可以转化为：找链表的第 L-N 个结点（这里完全不用想下标是啥，统一按照“第几个”来想）。

  此时我们自然可以先遍历一次链表计算出 L，再遍历一次找到目标结点，但更巧妙的方法是用快慢指针：快指针先走 N 步，之后快慢指针一起每次走一步，直到快指针走到最后一个结点。

  可以这么想：

  • 由于有可能会删除头结点，因此首先添加一个 dummy 结点；

  • 添加了 dummy 后，链表有 L+1 个结点，从 dummy 开始，需要走 L 步到达尾结点；

  • 我们需要找的结点变成了第 L-N+1 个结点，从 dummy 开始，需要走 L-N 步到达；

  • 快指针先走 N 步，还需要走 L-N 步到达尾结点，因此慢指针也要走 L-N 步，此时慢指针位于第 L-N+1 个结点，正好满足。

  关键之处在于要想清楚“走几步”和“到达第几个结点”之间的关系。因为我们最熟悉和喜欢的是“循环n次”，也就是“走几步”，搞清楚这个关系后，我们可以自然的写 for _ in range(n) 了。

• 快指针和慢指针同时走，快指针每次走多步

  876. 链表的中间结点

  找中间结点是快慢指针的经典应用，主要不好想的点在于链表可能有奇数个或偶数个结点，当结点个数为奇数时，中间结点为第 $\frac{L+1}{2}$ 个；当结点个数为偶数时，中间结点为第 $\frac{L}{2}$ 和第 $\frac{L}{2}+1$ 个，但题目要求为找第二个中间结点。

  首先快慢指针都从 head 出发，快指针每次走两步，慢指针每次走一步，直到快指针走到尾结点或者 None（即尾结点的下一个），此时慢指针指向的就是中间结点（总结点个数为偶数时是第二个）。

  def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
      return slow

• 套圈问题

  142. 环形链表 II

  用快慢指针可以方便判断链表是否有环：初始时快慢指针都在 head，快指针每次走两步，慢指针每次走一步（跟找中点一样），如果链表有环，那么一定有一刻快慢指针相等（停留在环上的某个结点，相当于快指针套了慢指针 n 圈）。

  但如果我们想找环的第一个结点该怎么办呢？我们只能保证快慢指针相遇处位于环上，但不一定是第几个。其实这是很简单的小学数学：设从头到环需要走 $a$ 步，绕环一圈要走 $c$ 步，从头结点到相遇位置，慢指针一共走了 $b$ 步，那么快指针就走了 $2*b$ 步。由于快指针和慢指针相遇是因为快指针在环上把慢指针套圈了，因此 $b=kc, k\in N$，慢指针位置和环入口处的距离就是 $kc - a$，因此慢指针再走 $a$ 步就一定会回到环入口处。我们虽然不知道 $a$ 等于多少，但只要让一个新的指针指向头结点，和慢指针一起走，每次都走一步，当它们第一次相遇时的位置就一定是环入口结点。

  说了这么多，其实就两步：第一步让快慢指针相遇后停下（和单纯判断环一样），第二步让指向头结点的指针和慢指针同步走，第一次相遇的位置就是答案。

  

def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            m = head
            while m is not slow:
                m = m.next
                slow = slow.next
            return m
    return None

合并两个升序链表

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummmy = ListNode()
    prev = dummmy
    while l1 and l2:
        if l1.val <= l2.val:
            prev.next = l1
            l1 = l1.next
        else:
            prev.next = l2
            l2 = l2.next
        prev = prev.next
    prev.next = l1 or l2
    return dummmy.next

二分

二分查找用于在一个单调区间中寻找分界点，常用于可被转化为诸如“大于等于 x 的最小值下标”、“小于等于 x 的最大值下标”等问题。也常见于查找有序或部分有序的数组中是否存在某个值。但不要拘泥于比大小，一般的，只要能够通过某种方式确定要找的目标在 mid 左边还是右边（二分条件是否满足），就可以成为二分查找的用武之地。

设有一个判定函数 check(mid)，并且它具有单调性，例如：

• 当 mid 越大，check(mid) 从 False 变成 True
• 或者从 True 变成 False

那么二分的目标就是找这个转折点：

• False False False True True True，找第一个满足 check(mid) == True 的位置（找最左真）；
• True True True False False False，最后一个满足 check(mid) == True 的位置（找最右真）。

关于二分答案：

二分查找是在下标空间二分，而二分答案是在值域上二分，本质都是利用单调性。问题求什么，就二分什么。只要想二分条件函数怎么写，其它都是套模版。

34. 在排序数组中查找元素的第一个和最后一个位置

闭区间二分模版：

def searchRange(nums: List[int], target: int) -> List[int]:
    ans = []
    l, r = 0, len(nums) - 1
    # 找开始位置
    while l < r:
        mid = (l + r) // 2
        if nums[mid] >= target:
            r = mid
        else:
            l = mid + 1
    if not nums or nums[l] != target:
        return [-1, -1]
    ans.append(l)
    # 找结束位置
    l, r = 0, len(nums) - 1
    while l < r:
        mid = (l + r + 1) // 2
        if nums[mid] <= target:
            l = mid
        else:
            r = mid - 1
    ans.append(l)
    return ans

• 关于这个模版的边界处理

  当出现 l = mid 时，需要写成 mid = (l + r + 1) // 2，即 math.ceil((l + r) / 2)。例如 l=3, r=4 时，mid = (l + r) // 2 = 3，l=mid 就会死循环。同理，当出现 r = mid 时，就需要写成向下取整的版本。

• 找不到会怎样

  需要注意的是二分最后是有可能找不到的，因此很多时候需要在循环结束后额外判断 if nums[l] == target。当数组中不存在满足二分条件的元素时，l 要么停在 0，要么停在 n-1 处（n 为数组长度）。这样做的好处是可以放心的访问 nums[l]（数组不能为空），不用担心越界，坏处是当 l=n-1 时需要特判找没找到（不能确定是因为找到了停在 n-1 处的还是没找到停在 n-1 处的）。

库函数写法：

def searchRange(nums: List[int], target: int) -> List[int]:
    start = bisect_left(nums, target)
    if start == len(nums) or nums[start] != target:
        return [-1, -1]
    end = bisect_right(nums, target) - 1
    return [start, end]

• bisect_left(nums, target) 找的是第一个 ≥ target 的位置。也就是在一个递增数组中尝试去插入 target（尽量往左插）的插入位置下标；
• bisect_right(nums, target) 找的是第一个 > target 的位置。也就是在一个递增数组中尝试去插入 target（尽量往右插）的插入位置下标。

这两个函数的返回值可能越界，例如返回 n；并且对于有些二分答案的题目无法直接套用，不可过于依赖库函数。

滑动窗口

只有满足单调性，才能用滑窗来做。即窗口变长或变小，与合法性的变化是单调的。如果随着窗口单调变化，一会合法一会不合法，那就要考虑别的做法了。

定长滑窗

不定长滑窗

越短越合法/求最长

不断扩充右端点，在扩充的过程中更新答案，直到不合法。之后开始移动左端点缩小窗口，直到再次合法。

越长越合法/求最短

不断扩充右端点，直到合法。之后开始移动左端点缩小窗口，在缩的过程中更新答案，直到不合法。

二叉树

二叉树定义：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

二叉树的遍历

def traversal(root: Optional[TreeNode]):
    if not root:
        return
    # print(root.val)	前序
    traversal(root.left)
    # print(root.val)	中序
    traversal(root.right)
    # print(root.val)	后序

• 时间复杂度：$O(n)$

• 空间复杂度：$O(h)$，$h$ 为树高

  • 最优情况：$O(logn)$（平衡树）
  • 最坏情况下 $O(n)$（退化成一条链）

自顶向下 DFS（先序）

特点：

• 父节点的信息传给子节点；
• 递归参数里往往带着“当前状态”；
• 一般递归函数可以没有返回值；
• 常见于：深度、路径、路径和、根到叶的统计等；

模板：

def dfs(root: Optional[TreeNode], depth: int) -> None:
    if not root:
        return

    # 进入当前节点，更新状态 / 答案

    dfs(root.left, depth + 1)
    dfs(root.right, depth + 1)

例：求最大深度（写法一：自顶向下）

def maxDepth(root: Optional[TreeNode]) -> int:
    ans = 0

    def dfs(node: Optional[TreeNode], depth: int) -> None:
        nonlocal ans
        if not node:
            return
        ans = max(ans, depth)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    if not root:
        return 0
    dfs(root, 1)
    return ans

这一类题的识别信号：如果题目在问“从根走到当前节点时，状态是什么？”、“路径上记录了什么？”、“当前深度是多少？”，一般优先想自顶向下 DFS。

自底向上 DFS（后序）

特点：

• 先拿左右子树结果，再计算当前节点结果；
• 返回值表示“当前子树的信息”；
• 常见于：高度、平衡性、直径、最近公共祖先、子树和 / 子树大小等；

模板：

def dfs(root: Optional[TreeNode]):
    if not root:
        return base

    left = dfs(root.left)
    right = dfs(root.right)

    # 根据左右子树结果计算当前节点结果
    return value

例：求最大深度（写法二：自底向上）

def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

这一类题的识别信号：如果题目在问“当前节点的答案依赖左右子树的答案”、“要先知道左右子树情况，再判断当前节点”、“返回某种子树信息给父节点”，一般优先想自底向上 DFS。

回溯

树上的回溯本质上就是：自顶向下 DFS + 路径状态维护 + 离开节点时恢复现场

模板：

def dfs(root: Optional[TreeNode]):
    if not root:
        return

    path.append(root.val)   # 做选择

    if is_leaf(root):
        # 收集答案
        pass

    dfs(root.left)
    dfs(root.right)

    path.pop()              # 恢复现场

例：113. 路径总和 II

def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
    ans = []
    path = []
    def dfs(root: Optional[TreeNode], res: int):
        if not root:
            return

        path.append(root.val)

        if not root.left and not root.right:
            if res + root.val == targetSum:
                ans.append(path[:])
        else:
            dfs(root.left, res + root.val)
            dfs(root.right, res + root.val)

        path.pop()

    dfs(root, 0)
    return ans

• 时间复杂度：$O(n^2)$. 每个结点会遍历一次，到叶子结点会进行一次复制数组操作，因此最坏情况下是 O(n^2)；
• 空间复杂度：$O(n)$

二叉搜索树（BST）

性质：

• 左子树所有节点值 < root.val
• 右子树所有节点值 > root.val
• 中序遍历是严格递增序列（默认 BST 不含重复值）

中序遍历 BST 是一个严格递增的序列。

98. 验证二叉搜索树

class Solution:
    pre = -math.inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        if not self.isValidBST(root.left):  # 左
            return False
        if root.val <= self.pre:  # 中
            return False
        self.pre = root.val
        return self.isValidBST(root.right)  # 右

230. 二叉搜索树中第 K 小的元素

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    cnt = 0
    ans = 0
    def inorder(root: Optional[TreeNode]):
        nonlocal cnt, ans
        if not root or cnt > k: # 找到后提前返回
            return
        inorder(root.left)
        cnt += 1
        if cnt == k:
            ans = root.val
        inorder(root.right)

    inorder(root)
    return ans

层序遍历（BFS)

用队列按层处理。

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    q = collections.deque([root])
    ans = []
    while q:
        vals = []
        n = len(q)
        for _ in range(n):
            cur = q.popleft()
            vals.append(cur.val)
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)
        ans.append(vals)
    return ans

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

深度、高度的区分

• 深度（depth）：从根到当前节点的边数 / 层数，适合自顶向下；
• 高度（height）：从当前节点到叶子节点的最长路径长度，适合自底向上。

深度是“从上往下传”，高度是“从下往上算”。

根据前中后序构造二叉树

在二叉树不含有重复元素的条件下：

• 给定前序+中序，可以唯一确定一颗二叉树；
• 给定中序+后序，可以唯一确定一颗二叉树；
• 给定前序+后序，不能唯一确定。

这种题的关键在于根据前中后序的性质，来确定左右子树的范围，从而得到子树的前中后序遍历。一旦左右子树的遍历顺序确定，这就变成了一个递归 dfs 的问题。

从前序与中序遍历序列构造二叉树

子树前序的第一个元素是当前子树的根节点，找到根节点在中序中的位置，其前半部分就是左子树的中序，大小就是左子树的结点数。根据这一信息，左右子树的前序和中序就能确定下来了。

因为每次递归都需要在中序遍历中查找根节点的下标，因此提前用哈希表处理好。

传递区间下标时，规定为左闭右开[left, right)是最方便的。算区间大小就是 right-left，根据左端点和大小算右端点就是 right=left+size，同理 left=right-size，不用反复考虑 +1 -1 问题。使用 range 或列表切分时也可以直接 range(left, right) 和 nums[left: right]。

模版如下：

def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    index = {x: i for i, x in enumerate(inorder)}
    def dfs(pl: int, pr: int, il: int, ir: int) -> Optional[TreeNode]:
        # 左闭右开
        if pl == pr:
            return None
        root = preorder[pl]
        idx = index[root]
        left_size = idx - il
        left = dfs(pl + 1, pl + 1 + left_size, il, idx)
        right = dfs(pl + 1 + left_size, pr, idx + 1, ir)
        return TreeNode(root, left, right)

    return dfs(0, len(preorder), 0, len(inorder))

从中序与后序遍历序列构造二叉树

和前序+中序同理，根节点为当前后序遍历的最后一个元素，由此可以通过查找中序遍历得到左子数的大小，从而得到左右子树的两种遍历：

def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    index = {x: i for i, x in enumerate(inorder)}
    def dfs(il: int, ir: int, pl: int, pr: int) -> Optional[TreeNode]:
        # 左闭右开
        if pl == pr:
            return None
        root = postorder[pr - 1]
        idx = index[root]
        left_size = idx - il
        left = dfs(il, idx, pl, pl + left_size)
        right = dfs(idx + 1, ir, pl + left_size, pr - 1)
        return TreeNode(root, left, right)

    return dfs(0, len(inorder), 0, len(postorder))

根据前序和后序遍历构造二叉树

这里和上面两种略有不同。由于根据前序和后序无法唯一确定二叉树结构，但此题要求随便生成一个合法的就可以。因此不妨规定对每个结点，都先有左孩子，再有右孩子，整棵树的形状“左对齐”。因此，在当前树的前序遍历中，根节点的下一个结点是根节点的左孩子。

我们的核心目标并未发生变化，都是要通过某种方式确认左子树的大小，从而得到左右子树的两种遍历。在这里，我们可以在后序遍历中找到左孩子的位置，那么左子树的大小就是从后续遍历的开始到这个位置。这样核心信息就已经确定，剩下的就是计算下标了。

需要注意的是，由于我们在递归中是通过当前前序遍历中的第二个元素来完成操作的，因此当到达叶子结点时（此时前序遍历只有一个元素），无法通过主流程完成操作，需要作为终止条件返回。

同时，空结点的终止条件也不能少。叶子结点的边界条件只能覆盖左子树叶子结点的情况，但当没有右子树时，依然会遍历到空结点。

def constructFromPrePost(preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    if not preorder:
        return None
    index = {x: i for i, x in enumerate(postorder)}
    def dfs(prel: int, prer: int, postl: int, postr: int) -> TreeNode:
        # 左闭右开，到空结点和叶子结点返回
        if prel == prer:
            return None
        if prel + 1 == prer:
            return TreeNode(preorder[prel])
        left_child = preorder[prel + 1]
        idx = index[left_child]
        left_size = idx - postl + 1
        left = dfs(prel + 1, prel + 1 + left_size, postl, postl + left_size)
        right = dfs(prel + 1 + left_size, prer, postl + left_size, postr - 1)
        return TreeNode(preorder[prel], left, right)

    return dfs(0, len(preorder), 0, len(postorder))

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

最近公共祖先（LCA)

本质上是自底向上 DFS（后序）。

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root in (None, p, q):
        return root

    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)

    if left and right:
        return root

    return left or right

每次递归的含义是：当前子树是否找到 p 或 q？如果都找到了，当前根节点就是 LCA；如果只找到一个，那就返回交由父结点处理；如果一个都没找到，那就返回 None 告诉父结点这没有。

虽然不同情况下递归函数返回的含义略有不同，但在这一模版下恰好是正确的。最终返回的就是 LCA。后序返回值表示：当前子树里是否包含目标节点，或者已经求出了答案。

数据结构

栈

单调栈

十六字真言：

及时去掉无用数据，
保证栈中元素有序。

堆

网格图

DFS

BFS

图论

DFS

找连通块

判断是否有环

回溯

两种思路：

• 选或不选

• 枚举选哪个

子集型回溯

组合型回溯

动态规划

很多动态规划问题，都可以先用记忆化搜索来理解和刻画。在 Python 中，这通常就是 dfs + @cache。当不同搜索路径会反复到达同一状态时，记忆化搜索就能避免重复计算，把原本指数级的搜索压缩为“每个状态只算一次”。

从 dfs 的角度思考 dp 是一种很好的训练方式，它能帮助我们逐步理解：原问题是如何被拆分成子问题的，状态为什么要这样设计，以及动态规划相比暴力搜索到底优化在什么地方。可以说，对于很多动态规划问题，不带记忆化的纯 dfs 可以看作其“暴力解法”：它会在大量重复子问题上反复搜索（好比双重循环之于双指针）；而加入记忆化后，本质上已经是在做动态规划，只不过仍然保留了递归实现的形式。

从这个角度看，动态规划并不是一种凭空出现的新技巧，而是对“重复子问题”的系统化处理。直观来讲，记忆化搜索是自顶向下地分解问题，先一路“递”到递归边界，再在“归”的过程中计算答案；而动态规划是自底向上，按顺序填表，省去了“递”的过程。二者本质相通，主要区别在于实现方式。

理论上，记忆化搜索通常可以达到与动态规划相同的时间复杂度。但由于递归调用、缓存查询以及递归栈的存在，它的实际运行常数往往更大，空间消耗通常也更高；当递归层数过深时，还可能导致爆栈。因此，在能够写成递推的情况下，动态规划往往更加高效和稳定。

在后面的题目中，我们会尽量先定义 dfs 的含义，写出记忆化搜索，再视情况改写为递推形式的动态规划。

前情提要：从 DFS 到记忆化搜索

什么样的 DFS 能够转变为记忆化搜索？

1. 同一个状态会被不同路径重复到达；
2. 一旦状态确定，答案就唯一确定。

记忆化搜索中 DFS 的设计技巧

逐步理解 dfs：二叉树 dfs —> 网格图 dfs —> 回溯 —> 记忆化搜索与动态规划

虽然写个递归函数，在上面加上 @cache 似乎就变成记忆化搜索了。但要知道，@cache 不是灵丹妙药。dfs 的设计直接决定了记忆化能否起作用，进而决定了题目能否做对、能够达到最优时间复杂度。

在 dfs 的设计上，我总结了以下几点经验：

1. 尽量不要在 dfs 内部依赖或修改全局变量，而应把信息体现在递归参数或返回值中（回溯问题除外）；
2. 要求什么，dfs 就返回什么；能用返回值表达的信息，就尽量不要额外放进递归参数里；
3. 尽量让 dfs 返回子问题的答案，并在回溯时合并结果，而不是携带过多局部状态一路向下传递。

这样做有几个好处：

1. 能迫使我们先想清楚自己写的 dfs 的定义：当前操作是什么、子问题是什么、状态该如何设计。这样在写的过程中，也更容易发现问题、简化状态、判断是否可以剪枝；
2. 有助于压缩状态维度。记忆化搜索的时间复杂度通常可以看作“状态数 × 单个状态的转移代价”，因此状态设计越精炼，缓存越有效；
3. 便于进一步改写成动态规划，从而更自然地理解动态规划为什么更优。

区间贪心

你可以用这句口诀：

🪟 滑动窗口：不对就缩
🧩 边界贪心：到点就结