递归的核心理解#

什么是递归#

递归问题是指子问题和最终问题相似时，且子问题容易解决时，可以先递到子问题，然后归到原问题来求解。

更直白地说，递归就是"函数自己调用自己"。但是刷题里真正重要的不是这个定义，而是要能看出来：当前问题能不能拆成一个或多个和原问题形式相同、规模更小的问题。

比如求链表长度：

Python3 点击展开代码

4 lines 展开代码

def length(head):
    if not head:
        return 0
    return 1 + length(head.next)

这个函数的意思不是"我脑子里一层一层模拟调用栈"，而是：

1
当前链表长度 = 1 + 后面链表的长度

所以写递归最重要的习惯是：相信递归函数已经能解决子问题。我们只需要想清楚当前层要做什么，以及什么时候停止。

递归三要素#

递归一般可以拆成三个问题：

1
1. 递归函数的定义是什么？
2
2. 递归出口是什么？
3
3. 当前层如何利用子问题结果？

第一点最重要。很多递归写乱，本质上不是不会写代码，而是一开始没有定义清楚函数到底返回什么、负责什么。

比如二叉树最大深度：

Python3 点击展开代码

4 lines 展开代码

def maxDepth(root):
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

这里递归函数的定义是：

1
maxDepth(root) 返回以 root 为根节点的树的最大深度

有了这个定义后，代码就自然了：

1
当前树最大深度 = 左子树最大深度 和 右子树最大深度 的较大值 + 1

所以以后写递归时，可以先写一句中文定义：

1
这个函数接收什么？
2
这个函数返回什么？
3
这个函数处理的是哪一段/哪一棵树/哪一个状态？

递归函数的定义方式#

递归函数通常有几种定义方式。

第一种，定义为"处理某个结构"：

Python3 代码示例

2 lines

def dfs(root):
    # 处理以 root 为根的整棵树

二叉树题最常见，比如最大深度、翻转二叉树、判断相同的树。

第二种，定义为"处理某个区间"：

Python3 代码示例

2 lines

def dfs(left, right):
    # 处理 [left, right] 这一段

分治题、构造树、归并排序、快排经常这样写。

第三种，定义为"从某个位置开始处理"：

Python3 代码示例

2 lines

def dfs(index):
    # 处理从 index 开始的后续问题

组合、切割、字符串匹配、动态规划递归版经常这样写。

第四种，定义为"当前路径/当前选择状态"：

Python3 代码示例

2 lines

def backtrack(path, used):
    # 当前已经选了 path，used 表示哪些元素用过

排列、N皇后、数独、分桶问题经常这样写。

第五种，定义为"两个对象之间的关系"：

Python3 代码示例

2 lines

def dfs(p, q):
    # 判断 p 和 q 之间是否满足某种关系

比如对称二叉树、相同的树、最长公共子序列、编辑距离。

递归函数定义得越准，后面的出口和递推关系就越容易写。

递归出口#

递归出口就是最小子问题，也就是不用再继续拆的问题。没有递归出口，就会无限递归。

常见出口有几类。

结构为空：

Python3 代码示例

2 lines

if not root:
    return 0

区间非法：

Python3 代码示例

2 lines

if left > right:
    return None

位置到头：

Python3 代码示例

2 lines

if index == len(nums):
    return

目标达成：

Python3 点击展开代码

3 lines 展开代码

if target == 0:
    ans.append(path[:])
    return

状态已经算过：

Python3 代码示例

2 lines

if state in memo:
    return memo[state]

递归出口要和函数定义保持一致。比如函数定义是"返回链表长度"，空链表就应该返回 0；如果函数定义是"返回是否存在路径"，走到目标就应该返回 True。

这里最容易错的是出口返回值。出口不是随便 return，而是要返回一个能被上一层正确使用的值。

递归返回值#

递归函数可以有返回值，也可以没有返回值。

有返回值时，通常是子问题的答案要交给上一层使用：

Python3 点击展开代码

6 lines 展开代码

def maxDepth(root):
    if not root:
        return 0
    left = maxDepth(root.left)
    right = maxDepth(root.right)
    return max(left, right) + 1

没有返回值时，通常是靠外部变量或者参数里的 path 收集答案：

Python3 点击展开代码

6 lines 展开代码

def backtrack(start):
    ans.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()

所以可以这样判断：

1
如果当前层需要子问题结果，就让递归函数 return。
2
如果只是枚举所有可能并收集答案，可以不 return，用 path 和 ans。

当然，回溯也可以有返回值，比如搜索是否存在一条路径时，找到后直接返回 True，可以提前剪枝。

递归前序位置与后序位置#

递归里经常说前序位置、后序位置，其实就是"递归调用前做事"还是"递归调用后做事"。

Python3 点击展开代码

9 lines 展开代码

def dfs(root):
    if not root:
        return

    # 前序位置：刚进入当前节点
    dfs(root.left)
    # 中序位置：左子树处理完，右子树还没处理
    dfs(root.right)
    # 后序位置：左右子树都处理完

前序位置适合自顶向下传递信息，比如当前路径和、当前深度、当前选择。

Python3 点击展开代码

4 lines 展开代码

path.append(root.val)
dfs(root.left)
dfs(root.right)
path.pop()

后序位置适合自底向上汇总信息，比如树的高度、节点数量、是否平衡、最大路径和。

Python3 点击展开代码

3 lines 展开代码

left = dfs(root.left)
right = dfs(root.right)
return max(left, right) + 1

可以简单记：

1
要把信息带下去，用前序。
2
要从子树收结果，用后序。

递归调用栈#

递归调用不是"魔法"，它本质上是系统帮我们维护了一个调用栈。每调用一次函数，就会把当前函数的局部变量、执行位置、参数保存起来，等子函数返回后再继续执行。

比如：

Python3 点击展开代码

6 lines 展开代码

def f(n):
    if n == 0:
        return
    print("before", n)
    f(n - 1)
    print("after", n)

调用 f(3) 的输出是：

1
before 3
2
before 2
3
before 1
4
after 1
5
after 2
6
after 3

这就是"递"和"归"：

1
递：一路进入更小的问题
2
归：从最小问题开始一层一层返回

所以很多题不建议一开始就把每一层调用全部脑补完，这样很容易晕。更好的方式是先相信函数定义，再看当前层如何组合答案。

递归和循环的关系#

递归和循环都能表达重复过程。

循环更适合线性、明确次数的问题：

Python3 代码示例

2 lines

for i in range(n):
    ...

递归更适合天然有层级结构、分支结构的问题：

Python3 代码示例

2 lines

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

比如遍历数组，用循环更自然；遍历二叉树，用递归更自然。

从本质上说，递归可以转成循环，只是需要我们自己维护栈：

Python3 点击展开代码

4 lines 展开代码

stack = [root]
while stack:
    node = stack.pop()
    ...

而递归就是系统帮我们维护这件事。所以递归代码通常更短、更贴合问题结构，但代价是会消耗调用栈空间，数据规模太大时可能爆栈。

递归、分治、回溯、动态规划的区别#

这几个概念很容易混在一起。我的理解是：递归是一种写法，分治、回溯、动态规划是几种不同的问题思想，它们都可以用递归来实现。

递归：

1
函数自己调用自己。

分治：

1
把一个大问题拆成几个互相独立的小问题，分别解决后合并。

典型例子是归并排序：

1
排序左半边 -> 排序右半边 -> 合并两个有序数组

回溯：

1
在一棵选择树上做选择，走不通就撤销选择，换下一条路。

典型例子是全排列、组合、N皇后。

动态规划：

1
有重复子问题，并且可以通过保存子问题结果避免重复计算。

递归版动态规划通常叫记忆化搜索。

可以用一个判断方式区分：

1
子问题互相独立，最后合并：分治。
2
需要枚举选择，选完还要撤销：回溯。
3
子问题大量重复，需要缓存：动态规划。
4
只是顺着结构自然往下走：普通递归。

比如二叉树最大深度，是普通结构递归；归并排序是分治递归；全排列是回溯递归；斐波那契加 memo 是记忆化搜索。

结构递归：顺着数据结构往下走#

链表递归#

LC206 - 反转链表#

正常而言，这一题可以使用简单的三指针翻转解决，但是既然本专栏是递归专题，肯定是用递归的方法来做。我们思考，如果我们需要翻转的链表，实际上就是需要一个函数每次返回翻转后的链表的头结点。这样，我们就能定义一个递归函数，自己调用自己来完成任务。

Python3 点击展开代码

10 lines 展开代码

# 定义函数为返回翻转后的链表的头结点
def reverseList(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    new_head = self.reverseList(head.next)
    # 原本的head.next现在在末尾
    head.next.next = head
    # 断开原本链接防止成环
    head.next = None
    return new_head

这道题的递归思路稍微有点绕，而且时空也不优秀，但是麻雀虽小，武藏巨拳。

LC24 - 两两交换链表中的节点#

在双指针专题中，我们写的就是递归写法，也是这类题目最简单的写法：

Python3 点击展开代码

14 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def swapPairs(self, head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    curr = head
    prev = None
    for _ in range(2):
        curr.next, prev, curr = prev,curr, curr.next
    head.next = swapPairs(curr)
    return prev

LC25 - K个一组翻转链表#

Python3 点击展开代码

19 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(self, head: ListNode,k:int) -> ListNode:
    # 如果剩余少于k个直接退出
    p = head
    for _ in range(k):
        if not p:
            return head
        p = p.next

    curr = head
    prev = None
    for _ in range(k):
        curr.next, prev, curr = prev,curr, curr.next
    head.next = reverseKGroup(curr,k)
    return prev

LC21 - 合并两个有序链表#

双指针合并自然是最简单的方式，但是，我们也可以利用递归结构来代替指针移动。

Python3 点击展开代码

12 lines 展开代码

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    if not list1:
        return list2
    if not list2:
        return list1

    if list1.val <= list2.val:
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    else:
        list2.next = mergeTwoLists(list1, list2.next)
        return list2

双指针：自己维护 p，一步步接节点。递归：每一层只决定当前头节点是谁，后面的合并交给递归。

不过这样做的话，空间复杂度更差了。一般两个链表的合并，我们还是直接用双指针。

LC23 - 合并K个升序链表#

涉及到了k个升序链表合并，就必须要用递归去做了（其实也可以用堆）。为了让递归树尽量平衡，我们应该每次在中间断开拆解子问题。当只有两个链表的时候，自然而然使用合并两个升序链表。

Python3 点击展开代码

33 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge2Lists(list1:ListNode,list2:ListNode)->ListNode:
    dummy = ListNode()
    p = dummy
    while list1 and list2:
        if list1.val<=list2.val:
            p.next = list1
            list1 = list1.next
        else:
            p.next = list2
            list2 = list2.next
        p = p.next
    p.next = list1 if list1 else list2
    return dummy.next

# 合并k个有序链表
def mergeKLists(lists:ListNode[ListNode])->ListNode:
    k = len(lists)
    if k == 0:
        return None
    if k == 1:
        return lists[0]
    if k == 2:
        return merge2Lists(lists[0],lists[1])
    # 大于两个链表开始递归处理
    mid = k//2
    left = mergeKLists(lists[:mid])
    right = mergeKLists(lists[mid:])
    return merge2Lists(left,right)

LC234 - 回文链表#

这一题最简单的做法是找中点、（断开）、翻转、判断。但是，也可以使用递归的方式来做。

我们知道，递归可以"反向"访问到链表的元素，因此我的思路是，先递归一路走到链表尾部，然后回来的时候，从后往前访问节点，同时用left从前往后走。如果这个过程left.val和right.val都相等，那就是回文链表。

Python3 点击展开代码

20 lines 展开代码

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(self, head: ListNode) -> bool:
    left = head
    def dfs(right:ListNode) -> bool:
        nonlocal left
        if not right:
            return True
        # 这里我们要将最后失败的结果一路传回来，所以不能简单递归dfs(right.next)，还要return一个值
        if not dfs(right.next):
            return False
        # 递归完成，从最后一位往前看
        if left.val != right.val:
            return False
        left = left.next
        return True
    return dfs(head)

这样写的话，空间上更差一点，但是好在不会破坏原本的链表的结构。

二叉树递归#

LC104 - 二叉树的最大深度#

树本身就是递归定义的，所以很多题目树的题目都可以回归本质用递归做：

Python3 点击展开代码

6 lines 展开代码

def solution(root:TreeNode)->int:
    def dfs(node):
        if not node:
            return 0
        return 1+max(dfs(node.left),dfs(node.right))
    return dfs(root)

LC111 - 二叉树的最小深度#

这类问题代表的是多出口的递归，不一定要一直递归到底返回，以为本题要求的答案不一定会到叶子节点才结算。

Python3 点击展开代码

18 lines 展开代码

class TreeNode:
    def __init__(self, val = 0, left = None,right = None):
        self.val = val
        self.left = left
        self.right = right 

def solution(root:TreeNode)->int:
    def dfs(node):
        if not node:
            return 0
        if not node.left and not node.right:
            return 1
        if not node.left:
            return 1+dfs(node.right)
        if not node.right:
            return 1+dfs(node.left)
        return 1+min(dfs(node.left),dfs(node.right))
    return dfs(root)

LC226 - 翻转二叉树#

递归返回的时候从下往上调转左右即可：

Python3 点击展开代码

10 lines 展开代码

def invertTree(self, root: TreeNode) -> TreeNode:
    def dfs(node):
        if not node:
            return 
        dfs(node.left)
        dfs(node.right)
        # 递归完成，从后往前翻转
        node.left,node.right = node.right,node.left
    dfs(root)
    return root

LC100 - 相同的树#

代表两边同时进行递归判断的题目：

Python3 点击展开代码

12 lines 展开代码

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    def dfs(p,q)->bool:
        if not p and not q:
            return True
        if not p and q:
            return False
        if p and not q:
            return False
        if p.val!=q.val:
            return False
        return dfs(p.left,q.left) and dfs(p.right,q.right)
    return dfs(p,q)

LC101 - 对称二叉树#

两个指针同时进行递归判断，一个向左一个向右，值和形状应该始终保持一致。

Python3 点击展开代码

14 lines 展开代码

def isSymmetric(self, root: TreeNode) -> bool:
    def dfs(p,q):
        if not p and not q:
            return True
        if not p and q:
            return False
        if p and not q:
            return False
        if p.val != q.val:
            return False
        return dfs(p.left,q.right) and dfs(p.right,q.left)
    if not root:
        return True
    return dfs(root.left,root.right)

LC543 - 二叉树的直径#

本题属于递归维持、返回的量，和题目要求的量不一样。但是递归可以保证一定可以考虑到最优解的情况（实际上就是遍历了），所以我们维持一个全局量来更新，然后dfs即可。

放在本题，直接想二叉树直径很难，可以将问题降级为"从node出发的最大节点数"，只要知道了这个量，任意节点都可以看自己的左右孩子的这个量，来判断需不需要更新最大路径。

Python3 点击展开代码

18 lines 展开代码

def diameterOfBinaryTree(self, root: TreeNode) -> int:
    # 递归函数为从node开始最长的节点数
    max_path = 0
    def dfs(node:TreeNode)->int:
        nonlocal max_path
        if not node:
            return 0
        left_path = dfs(node.left)
        right_path = dfs(node.right)

        # 因为边数等于节点数少1，题目求的是边数，所以不用+1
        max_path = max(max_path,
        left_path+right_path)

        return 1 + max(left_path,right_path)
    
    dfs(root)
    return max_path

LC110 - 平衡二叉树#

平衡二叉树是左右高度之差之中不大于1，对所有子树都有这约束。这道题是通过递归传递多种信息的典型。我们通过传递的量不仅要表示子树高度为多少，还要表达子树是否已经不平衡，于是不平衡传递-1，告诉上层也不用继续算了。

Python3 点击展开代码

19 lines 展开代码

def isBalanced(self, root: TreeNode) -> bool:
    def dfs(node: TreeNode) -> int:
        if not node:
            return 0

        left = dfs(node.left)
        if left == -1:
            return -1

        right = dfs(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1
        # 记录左右最大高度
        return max(left, right) + 1

    return dfs(root) != -1

LC236 - 二叉树的最近公共祖先#

同样是通过递归传递信息，这题需要传递的信息是"是否找到p/q"。如果找到了，就要返回自身。如果没找到，就不要返回。

Python3 点击展开代码

11 lines 展开代码

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == 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 if left else right

LC235 - 二叉搜索树的最近公共祖先#

上一题的逻辑适用于所有树的情况，这一题既然已经是BST，就可以利用值的性质。即如果p、q都是左子树，则答案一定在左边；反之一定在右边；如果一左一右，则root就是答案。

Python3 点击展开代码

8 lines 展开代码

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if p.val < root.val and q.val < root.val:
        return self.lowestCommonAncestor(root.left, p, q)

    if p.val > root.val and q.val > root.val:
        return self.lowestCommonAncestor(root.right, p, q)
    # 如果一左一右，则root就是答案
    return root

二叉搜索树递归#

LC98 - 验证二叉搜索树#

需要注意的是，BST是全局性质，因此递归过程中要维持一个上下界。

Python3 点击展开代码

9 lines 展开代码

def isValidBST(self, root: TreeNode) -> bool:
    def dfs(lo, hi, node):
        if not node:
            return True
        if not lo < node.val < hi:
            return False
        return dfs(lo, min(hi, node.val), node.left) and dfs(max(lo, node.val), hi, node.right)

    return dfs(float('-inf'), float('inf'), root)

LC700 - 二叉搜索树中的搜索#

正常的思路，注意递归的分支和返回即可。

Python3 点击展开代码

11 lines 展开代码

def searchBST(self, root: TreeNode, val: int) -> TreeNode:
    def dfs(node) -> TreeNode:
        if not node:
            return None
        if node.val == val:
            return node
        elif node.val < val:
            return dfs(node.right)
        else:
            return dfs(node.left)
    return dfs(root)

LC701 - 二叉搜索树中的插入操作#

带条件的递归，我们根据 BST 的大小关系一路递归到空位置，在空位置创建新节点；回溯时把插入后的子树逐层接回原树，最后返回根节点。

说白了，这是一题修改子树的递归题，而不是以前那样的找结果的递归题，所以感觉上可能有点稍微的差距，倒是和链表有点相似，就是返回修改过的部分。

Python3 点击展开代码

12 lines 展开代码

def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    def dfs(node):
        if not node:
            return TreeNode(val)
        # 根据值的位置选择要调整的半边
        if node.val < val:
            node.right = dfs(node.right)
        else:
            node.left = dfs(node.left)
        return node
    
    return dfs(root)

LC450 - 删除二叉搜索树中的节点#

和上一题一样，需要调整子树。

Python3 点击展开代码

30 lines 展开代码

def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
    def dfs(node):
        if not node:
            return None

        # 找到需要调整的半边
        if key < node.val:
            node.left = dfs(node.left)
            return node

        if key > node.val:
            node.right = dfs(node.right)
            return node

        # 找到要删除的节点
        if not node.left:
            return node.right

        if not node.right:
            return node.left

        # 左右子树都存在：右子树顶上来，左子树接到右子树最小节点下面
        p = node.right
        while p.left:
            p = p.left
        p.left = node.left

        return node.right

    return dfs(root)

LC230 - 二叉搜索树中第K小的元素#

直接中序遍历即可：

Python3 点击展开代码

14 lines 展开代码

def kthSmallest(self, root: TreeNode, k: int) -> int:
    ans = None
    def dfs(node):
        nonlocal k,ans
        if not node or ans is not None:
            return
        dfs(node.left)
        k-=1
        if k==0:
            ans = node.val
            return
        dfs(node.right)
    dfs(root)
    return ans

N叉树递归#

LC559 - N叉树的最大深度#

N叉树的结局方法，和二叉树其实差不多，用一个循环解决即可。

Python3 点击展开代码

9 lines 展开代码

def maxDepth(self, root: 'Node') -> int:
    def dfs(node):
        if not node:
            return 0
        max_children = 0
        for i in node.children:
            max_children = max(max_children,dfs(i))
        return 1+max_children
    return dfs(root)

LC589 - N叉树的前序遍历#

公式递归。

Python3 点击展开代码

10 lines 展开代码

def preorder(self, root: 'Node') -> list[int]:
    ans = []
    def dfs(node):
        if not node:
            return 
        ans.append(node.val)
        for child in node.children:
            dfs(child)
    dfs(root)
    return ans

LC590 - N叉树的后序遍历#

公公又式式

Python3 点击展开代码

10 lines 展开代码

def postorder(self, root: 'Node') -> list[int]:
    ans = []
    def dfs(node):
        if not node:
            return 
        for child in node.children:
            dfs(child)
        ans.append(node.val)
    dfs(root)
    return ans

分治递归：把问题拆成左右两半#

分治的基本模板#

分治递归的关键，不只是"拆开"，更是"怎么合并"。很多题递归本身不难，难的是左右子问题的答案如何拼回当前问题。

一个标准的分治题，通常都可以先问自己四个问题：

1
1. 这个问题能不能拆成左右两半？
2
2. 左半边要返回什么信息？
3
3. 右半边要返回什么信息？
4
4. 当前层如何利用左右信息合并答案？

一个基础模板如下：

Python3 点击展开代码

12 lines 展开代码

def divide_and_conquer(left, right):
    # 递归出口
    if left == right:
        return 单个区间的答案

    mid = (left + right) // 2

    left_info = divide_and_conquer(left, mid)
    right_info = divide_and_conquer(mid + 1, right)

    # 合并左右子问题答案
    return merge(left_info, right_info)

如果是排序类题目，merge 真的就是合并有序结果；如果是统计类题目，merge 还会顺手统计贡献；如果是区间最值类题目，merge 则是在左右子区间答案的基础上，再考虑是否存在"跨中点"的情况。

归并排序#

LC912 - 排序数组#

这一题就是大名鼎鼎的归并排序。每次切半，直到不能切为止，然后组装起来。

Python3 点击展开代码

21 lines 展开代码

def merge(nums1,nums2):
    nums = []
    i, j = 0, 0
    while i<len(nums1) and j<len(nums2):
        if nums1[i]<=nums2[j]:
            nums.append(nums1[i])
            i+=1
        else:
            nums.append(nums2[j])
            j+=1
    nums.extend(nums1[i:] if i<len(nums1) else nums2[j:])
    return nums

def sortArray(nums: list[int]) -> list[int]:
    n = len(nums)
    if n<= 1:
        return nums
    mid = n//2
    left = sortArray(nums[:mid])
    right = sortArray(nums[mid:])
    return merge(left,right)

后面有很多题目会在同一个函数中解决问题，因此我们学着利用python的特性，把分解与归并排序操作放在函数体内的同一个函数merge_sort中，这样更清晰：

Python3 点击展开代码

28 lines 展开代码

def solution(nums:list):
    def merge_sort(left,right):
        # 注意要写退出条件
        if left==right:
            return [nums[left]]
        mid = (left + right) // 2
        left_arr = merge_sort(left,mid)
        right_arr = merge_sort(mid+1,right)

        # 到这里，拆分已经完成，开始归并
        # 归并的过程，就是两个有序数组合并了
        merged = []
        i, j = 0, 0
        while i<len(left_arr) and j<len(right_arr):
            if left_arr[i]<=right_arr[j]:
                merged.append(left_arr[i])
                i += 1
            else:
                merged.append(right_arr[j])
                j += 1
        merged.extend(left_arr[i:])
        merged.extend(right_arr[j:])
        return merged
    
    if not nums:
        return []

    return merge_sort(0,len(nums)-1)

LC148 - 排序链表#

同样的归并排序：

Python3 点击展开代码

26 lines 展开代码

def merge(list1:ListNode,list2:ListNode)->ListNode:
    dummy = ListNode()
    p = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            p.next = list1
            list1 = list1.next
        else:
            p.next = list2
            list2 = list2.next
        p = p.next
    p.next = list1 if list1 else list2
    return dummy.next

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    slow, fast = head, head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next
    second = slow.next
    slow.next = None
    left = sortList(head)
    right = sortList(second)
    return merge(left,right)

同理单函数版：

Python3 点击展开代码

37 lines 展开代码

class ListNode:
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next

def solution(head:ListNode):
    def merge_sort(head:ListNode):
        # 只有一个节点或者空的时候不用切了
        if not head or not head.next:
            return head
        fast, slow = head, head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        second = slow.next
        slow.next = None
        leftList = merge_sort(head)
        rightList = merge_sort(second)

        # 切分完毕，开始合并
        dummy = ListNode()
        p = dummy
        l, r = leftList, rightList
        while l and r:
            if l.val <= r.val:
                p.next = l
                l = l.next
            else:
                p.next = r
                r = r.next
            p = p.next
        p.next = l if l else r
        return dummy.next
    
    if not head:
        return None
    return merge_sort(head)

LC23 - 合并K个升序链表#

跟上一题基本没啥区别，降到两两合并即可：

Python3 点击展开代码

28 lines 展开代码

def merge2Lists(list1:ListNode,list2:ListNode)->ListNode:
    dummy = ListNode()
    p = dummy
    while list1 and list2:
        if list1.val<=list2.val:
            p.next = list1
            list1 = list1.next
        else:
            p.next = list2
            list2 = list2.next
        p = p.next
    p.next = list1 if list1 else list2
    return dummy.next

# 合并k个有序链表
def mergeKLists(lists:ListNode[ListNode])->ListNode:
    k = len(lists)
    if k == 0:
        return None
    if k == 1:
        return lists[0]
    if k == 2:
        return merge2Lists(lists[0],lists[1])
    # 大于两个链表开始递归处理
    mid = k//2
    left = mergeKLists(lists[:mid])
    right = mergeKLists(lists[mid:])
    return merge2Lists(left,right)

快速排序#

快速排序是非常经典的板子，大部分自带排序函数底层都是快排实现的，因为其效率很高。

快排模板#

快排的本质，就是通过一次 partition，把 pivot 放到最终位置；再递归处理 pivot 左右两边。

先选一个 pivot，常见写法是默认选最后一个元素；用 i 标记"小于等于 pivot 区域"的下一个写入位置；用 j 从左到右扫描；遇到 <= pivot 的数，就和 nums[i] 交换，然后 i 往后走；最后把 pivot 和 nums[i] 交换。

Python3 点击展开代码

24 lines 展开代码

def quick_sort(nums: list[int]) -> list[int]:
    def partition(left: int, right: int) -> int:
        pivot = nums[right]
        i = left

        for j in range(left, right):
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

        nums[i], nums[right] = nums[right], nums[i]
        return i

    def dfs(left: int, right: int) -> None:
        if left >= right:
            return

        pivot_idx = partition(left, right)

        dfs(left, pivot_idx - 1)
        dfs(pivot_idx + 1, right)

    dfs(0, len(nums) - 1)
    return nums

LC215 - 数组中的第K个最大元素#

利用快速选择的性质，可以在不用完全排序前找到第k大的元素，这个方法也叫快速选择排序，可以在O(n)内解决这个问题。

Python3 点击展开代码

30 lines 展开代码

def findKthLargest(nums: list[int], k: int) -> int:  
    target = len(nums) - k

    # 将最后一个元素作为枢纽，返回正确位置
    def partition(left,right):
        pivot = nums[right]
        i = left
        for j in range(left,right):
            if nums[j] <= pivot:
                nums[i],nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i


    left = 0
    right = len(nums) - 1

    def quick_select(left: int, right: int) -> int:
        pivot_idx = partition(left, right)

        if pivot_idx == target:
            return nums[pivot_idx]

        if pivot_idx < target:
            return quick_select(pivot_idx + 1, right)
        else:
            return quick_select(left, pivot_idx - 1)

    return quick_select(0, len(nums) - 1)

然而，这样写，力扣上会时间超限。这就很难受了，因为快选平均才能On，最坏要On方。我们有时候会加入随机来保证枢纽随便选：

Python3 点击展开代码

4 lines 展开代码

# 随机选枢纽
random_idx = random.randint(left,right)
nums[random_idx], nums[right] = nums[right], nums[random_idx]
pivot = nums[right]

但是，这样还是会超时。这个写法在有大量重复元素的时候会发生退化。最好的方式，是把<=和else的两路划分，变成三路划分，如下：

Python3 点击展开代码

36 lines 展开代码

import random

def findKthLargest(nums: list[int], k: int) -> int:
    target = k - 1  # 降序后的第 k 大下标

    def quick_select(left: int, right: int) -> int:
        pivot = nums[random.randint(left, right)]

        lt = left      # nums[left:lt] > pivot
        i = left       # nums[lt:i] == pivot
        gt = right     # nums[gt+1:right+1] < pivot

        while i <= gt:
            if nums[i] > pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] < pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1

        # 现在：
        # [left, lt - 1] 都 > pivot
        # [lt, gt] 都 == pivot
        # [gt + 1, right] 都 < pivot

        if target < lt:
            return quick_select(left, lt - 1)
        elif target > gt:
            return quick_select(gt + 1, right)
        else:
            return nums[target]

    return quick_select(0, len(nums) - 1)

没错，这就是经典的荷兰国旗问题啊，三路划分让快排可以有效处理很多重复元素，直接把lt到gt之间的元素忽略掉。

二分递归#

LC704 - 二分查找#

经典二分查找，我们先直接写二分查找的板子：

Python3 点击展开代码

13 lines 展开代码

def search(self, nums: list[int], target: int) -> int:
    # 小于target往右找
    left, right = 0, len(nums)
    while left<right:
        mid = (left+right)//2
        if nums[mid]<target:
            left = mid + 1
        else:
            right = mid
    if left <len(nums) and nums[left] == target:
        return left
    else:
        return -1

但是放在了二分递归的板子里，是为了告诉你，这题也是非常符合递归的题：

Python3 点击展开代码

15 lines 展开代码

def binary_search(nums, target):
    def dfs(left, right):
        if left > right:
            return -1

        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return dfs(mid + 1, right)
        else:
            return dfs(left, mid - 1)

    return dfs(0, len(nums) - 1)

本质上和迭代写法等效，就是去两边找，但是迭代的写法更容易理解，且没有空间消耗，所以尽量写迭代吧。

LC35 - 搜索插入位置#

Python3 点击展开代码

9 lines 展开代码

def searchInsert(self, nums: list[int], target: int) -> int:
    left, right = 0, len(nums)
    while left<right:
        mid = (left + right)//2
        if nums[mid]<target:
            left = mid + 1
        else:
            right = mid
    return left

LC69 - x的平方根#

Python3 点击展开代码

11 lines 展开代码

def mySqrt(self, x: int) -> int:
    left, right = 0, x
    while left < right:
        mid = (left + right) // 2
        if mid*mid < x:
            left = mid + 1
        else:
            right = mid
    if left*left == x:
        return left
    return left-1

LC50 - Pow(x, n)#

这一题，是运用了快速幂的思想，将时间复杂度从O(n)降低到了O(logn)：

Python3 点击展开代码

16 lines 展开代码

def myPow(x: float, n: int) -> float:
    def dfs(n: int) -> float:
        if n == 0:
            return 1

        half = dfs(n // 2)

        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

    if n >= 0:
        return dfs(n)
    else:
        return 1 / dfs(-n)

分治统计#

LC169 - 多数元素#

本题属于答案一定在左或右，需要二次判断左右给出的信息。

多数元素的最优解法是投票法，我们让相同加票数，不同减票数，最后剩下的候选人就是多数元素。

Python3 点击展开代码

14 lines 展开代码

def majorityElement(self, nums: List[int]) -> int:
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    return candidate

不过就当是锻炼思维，这一题也是可以用分治法来做的。分治的思路是递归左半边的多数元素、右半边的多数元素，如果结果相同就直接返回，否则就在当前区间内分别统计它们出现次数，返回次数更多的那个。

Python3 点击展开代码

26 lines 展开代码

def majorityElement(nums: list[int]) -> int:
    def count_in_range(target: int, left: int, right: int) -> int:
        count = 0
        for i in range(left, right + 1):
            if nums[i] == target:
                count += 1
        return count

    def dfs(left: int, right: int) -> int:
        if left == right:
            return nums[left]

        mid = (left + right) // 2

        left_major = dfs(left, mid)
        right_major = dfs(mid + 1, right)

        if left_major == right_major:
            return left_major

        left_count = count_in_range(left_major, left, right)
        right_count = count_in_range(right_major, left, right)

        return left_major if left_count > right_count else right_major

    return dfs(0, len(nums) - 1)

LC53 - 最大子数组和#

本题属于答案可能在左、右或跨中点的归并题。

这一题，每个数字要么接着前面的结果继续，要么另起炉灶，所以很容易就能想到动态规划来做。

Python3 点击展开代码

8 lines 展开代码

def maxSubArray(self, nums: list[int]) -> int:
    # 我们让dp[i]表示以i结尾的最大数组和
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1,n):
        dp[i] = max(dp[i-1]+nums[i],nums[i])
    return max(dp)

这就是最好的方法了，但是，这题同样可以使用分治统计来做。最大子数组只有三种可能，要么最大子数组完全在左半边，要么完全在右半边，要么跨过中点。

Python3 点击展开代码

27 lines 展开代码

def maxSubArray(nums: list[int]) -> int:
    def dfs(left: int, right: int) -> int:
        if left == right:
            return nums[left]

        mid = (left + right) // 2

        left_max = dfs(left, mid)
        right_max = dfs(mid + 1, right)

        left_sum = float("-inf")
        curr = 0
        for i in range(mid, left - 1, -1):
            curr += nums[i]
            left_sum = max(left_sum, curr)

        right_sum = float("-inf")
        curr = 0
        for i in range(mid + 1, right + 1):
            curr += nums[i]
            right_sum = max(right_sum, curr)

        cross_max = left_sum + right_sum

        return max(left_max, right_max, cross_max)

    return dfs(0, len(nums) - 1)

这个方法的空间复杂度logn，时间复杂度nlogn。

然后，这个递归仍然可以优化，让时间变成on。需要返回每个区间返回四个信息：区间总和sum、区间最大后缀和prefix、区间最大后缀和suffix、区间最大子数组和best。

Python3 点击展开代码

20 lines 展开代码

def maxSubArray(nums: list[int]) -> int:
    def dfs(left: int, right: int):
        if left == right:
            x = nums[left]
            return x, x, x, x
            # total, prefix, suffix, best

        mid = (left + right) // 2

        l_sum, l_pre, l_suf, l_best = dfs(left, mid)
        r_sum, r_pre, r_suf, r_best = dfs(mid + 1, right)

        total = l_sum + r_sum
        prefix = max(l_pre, l_sum + r_pre)
        suffix = max(r_suf, r_sum + l_suf)
        best = max(l_best, r_best, l_suf + r_pre)

        return total, prefix, suffix, best

    return dfs(0, len(nums) - 1)[3]

剑指Offer 51 - 数组中的逆序对#

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

本题是归并的时候统计贡献，难度适合入门。合并的过程中不断判断left是否超过right，如果超过就是逆序。这里的i、j本身也就是合并有序数组的意思（本身这题就是归并排序的同时去做统计），然后一旦发现left[i]大于right[j]，那么left后面所有的数字都能和right[j]构成逆序对，所以可以直接加个数为len(left)-i。

Python3 点击展开代码

34 lines 展开代码

def reversePairs(nums: list[int]) -> int:
    count = 0

    def merge_sort(arr: list[int]) -> list[int]:
        nonlocal count

        if len(arr) <= 1:
            return arr

        mid = len(arr) // 2
        left = merge_sort(arr[:mid])
        right = merge_sort(arr[mid:])

        merged = []
        i, j = 0, 0

        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                # left[i] > right[j]
                # left[i:] 都能和 right[j] 构成逆序对
                count += len(left) - i
                merged.append(right[j])
                j += 1

        merged.extend(left[i:])
        merged.extend(right[j:])

        return merged

    merge_sort(nums)
    return count

LC315 - 计算右侧小于当前元素的个数#

本题依然属于归并过程中统计贡献题，比上一题难度高一点，核心思想是，在归并排序合并两个有序区间时，统计右半边有多少个数已经被放到当前左半边元素前面。

因为右半边的元素原本就在当前元素右侧。如果某些右半边元素比左半边当前元素小，并且已经先被合并走了，那它们就应该计入答案。

注意为了保留原始下标，我们不能只排序数字，而要排序(value,index)，本题还是归并排序。

Python3 点击展开代码

48 lines 展开代码

def countSmaller(nums: list[int]) -> list[int]:
    n = len(nums)
    ans = [0] * n
    arr = [(num, i) for i, num in enumerate(nums)]

    def merge_sort(left: int, right: int) -> list[tuple[int, int]]:
        if left == right:
            return [arr[left]]

        mid = (left + right) // 2
        left_part = merge_sort(left, mid)
        right_part = merge_sort(mid + 1, right)

        merged = []
        i, j = 0, 0
        right_smaller_count = 0

        while i < len(left_part) and j < len(right_part):
            if right_part[j][0] < left_part[i][0]:
                merged.append(right_part[j])
                # 记录先归并右边的元素个数
                right_smaller_count += 1
                j += 1
            else:
                value, idx = left_part[i]
                # 归并左边时加上已经归并过的右侧的记数
                ans[idx] += right_smaller_count
                merged.append(left_part[i])
                i += 1

        # 归并后续剩余元素

        while i < len(left_part):
            value, idx = left_part[i]
            ans[idx] += right_smaller_count
            merged.append(left_part[i])
            i += 1

        while j < len(right_part):
            merged.append(right_part[j])
            j += 1

        return merged

    if nums:
        merge_sort(0, n - 1)

    return ans

有人可能会疑惑，只在归并左侧元素时更新 ans 足够吗？其实是足够的。只有这种情况会对答案造成贡献：

当前元素在左半边；
更小的元素在右半边；
右半边元素先于它被合并。

而拆分过程中，元素最终会被切成一个一个的元素，不会经过这个判断的，也只有右侧最后一个元素，而这个元素右侧小于它的数字个数必定是0，所以是完全足够的。

选择递归：每一步做选择#

子集问题#

LC78 - 子集#

子集，实际上是一个每个元素可选可不选的问题，我们可以直接进行按位置的dfs。

Python3 点击展开代码

16 lines 展开代码

def subsets(self, nums: list[int]) -> list[list[int]]:
    ans = []
    path = []
    def dfs(i):
        if i == len(nums):
            ans.append(path[:])
            return
        # 选择
        path.append(nums[i])
        dfs(i+1)
        # 回溯
        path.pop()
        # 不选择
        dfs(i+1)
    dfs(0)
    return ans

除了这种递归方法之外，我们还可以遍历数组递归，以开头元素为基准dfs出所有情况。为了不回头看，用start来调整对应的位置即可：

Python3 点击展开代码

10 lines 展开代码

def subsets(self, nums: list[int]) -> list[list[int]]:
    ans = []
    path = []
    def dfs(start):
        ans.append(path[:])
        for i in range(start,len(nums)):
            path.append(nums[i])
            dfs(i+1)
            path.pop()
    return ans

总结一下，子集问题有两种常见递归视角。第一种是选/不选，每个元素都做一次二选一，答案在叶子节点收集。第二种是枚举下一个选择，从 start 开始向后选择一个元素加入 path，答案在每个递归节点收集。对于没有重复元素的 LC78，两种都可以；对于有重复元素的 LC90，for + start 写法更适合同层去重。

LC90 - 子集II#

子集II与子集问题只有轻微不同，给的数组nums可能包含重复元素，但解集不能包含重复的子集，所以一个简单的想法，先排序，然后开始暴力求子集，并去重：

Python3 点击展开代码

17 lines 展开代码

def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
    nums.sort()
    ans = set()
    path = []
    def dfs(i):
        if i == len(nums):
            ans.add(tuple(path[:]))
            return
        # 选择
        path.append(nums[i])
        dfs(i+1)
        # 回溯
        path.pop()
        # 不选择
        dfs(i+1)
    dfs(0)
    return [list(t) for t in ans]

但是，这样写的效率很低，有很多次无用递归。如果学到了NSum对于去重的方法，那么这一题就不会这么生硬去重，我们排序后，对于每次选择同样元素开始dfs的，直接跳过。

组合问题#

LC77 - 组合#

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

换句话说，不重复的1-n，让你选长度为k的子集。这么说就明白了，跟子集问题几乎没区别：

Python3 点击展开代码

13 lines 展开代码

def combine(self, n: int, k: int) -> list[list[int]]:
    path = []
    ans = []
    def dfs(start):
        if len(path) == k:
            ans.append(path[:])
            return
        for i in range(start,n+1):
            path.append(i)
            dfs(i+1)
            path.pop()
    dfs(1)
    return ans

LC39 - 组合总和#

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

抓住两点：无重复、可复选。其他的dfs的条件变一下就行。

Python3 点击展开代码

19 lines 展开代码

def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
    path = []
    ans = []
    total = 0
    def dfs(start):
        nonlocal total
        if total > target:
            return 
        if total == target:
            ans.append(path[:])
            return
        for i in range(start,len(candidates)):
            path.append(candidates[i])
            total += candidates[i]
            dfs(i)
            path.pop()
            total -= candidates[i]
    dfs(0)
    return ans

这么写是对的，不过效率还是可以继续提升，参考剪枝的方案，我们依旧先排序，然后再判断目前是否已经超过target。如果超过了，都不用继续递归进去。

Python3 点击展开代码

20 lines 展开代码

def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    path = []
    ans = []

    def dfs(start: int, total: int):
        if total == target:
            ans.append(path[:])
            return

        for i in range(start, len(candidates)):
            if total + candidates[i] > target:
                break

            path.append(candidates[i])
            dfs(i, total + candidates[i])
            path.pop()

    dfs(0, 0)
    return ans

LC40 - 组合总和II#

组合总和II和I相比，多了每个数字仅能使用一次，然后少了数字不重复。因此，我们要对重复元素进行剪枝：

Python3 点击展开代码

18 lines 展开代码

def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    path = []
    ans = []
    def dfs(start,total):
        if total == target:
            ans.append(path[:])
            return
        for i in range(start,len(candidates)):
            if i>start and candidates[i] == candidates[i-1]:
                continue
            if total + candidates[i] > target:
                break
            path.append(candidates[i]) 
            dfs(i+1,total+candidates[i])
            path.pop()
    dfs(0,0)
    return ans

这里进行了两种剪枝，continue那里是去重剪枝，虽然这个数不能选，但是后面的可能可以选；而break是超过目标剪枝，因为已经排序完成了，如果超过target，后面肯定不能选了，直接break掉就行。

LC216 - 组合总和III#

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

翻译一下，用1-9（没有重复元素），不能重复用。其实很简单：

Python3 点击展开代码

14 lines 展开代码

def combinationSum3(self, k: int, n: int) -> list[list[int]]:
    path = []
    ans = []
    def dfs(start,total):
        if total == n and len(path)==k:
            ans.append(path[:])
        for i in range(start,10):
            if total+i>n:
                break
            path.append(i)
            dfs(i+1,total+i)
            path.pop()
    dfs(1,0)
    return ans

排列问题#

LC46 - 全排列#

全排列和子集问题的差距在于，可以回头选元素了。所以也不用维护start，每次都从头找。但是要额外维持一个seen，防止复选。

Python3 点击展开代码

20 lines 展开代码

def permute(self, nums: list[int]) -> list[list[int]]:
    n = len(nums)
    seen = [False]*n
    path = []
    ans = []
    def dfs():
        if len(path) == n:
            ans.append(path[:])
            return
        
        for i in range(n):
            if seen[i]:
                continue
            seen[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            seen[i] = False
    dfs()
    return ans

LC47 - 全排列II#

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

也就是说，我们依旧是要进行去重了。但是，每一层都要从头扫，因为任意没用过的数都可能被选，所以我们不能能用start去重了，要改一下思路。

于是我们利用used去重，如果i-1的位置没有被使用，且i位置和i-1位置数字一样，那么这个数字也不能先用 — 换句话说，就是相同数字之间必须保持按原本顺序使用！所以就不会出现颠倒的两种情况。

Python3 点击展开代码

28 lines 展开代码

def permuteUnique(self, nums: list[int]) -> list[list[int]]:
    nums.sort()
    ans = []
    path = []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            ans.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])

            dfs()

            path.pop()
            used[i] = False

    dfs()
    return ans

切割问题#

LC131 - 分割回文串#

本题可以通过dfs，考虑到所有区间切分的情况，从而将所有符合条件的子区间加入到答案当中。

Python3 点击展开代码

28 lines 展开代码

def partition(self, s: str) -> list[list[str]]:
    def ishuiwen(nums):
        i,j = 0, len(nums)-1
        while i<j:
            if nums[i] != nums[j]:
                return False
            i+=1
            j-=1
        return True
    
    ans = []
    path = []

    def dfs(start):
        if start == len(s):
            ans.append(path[:])
            return 
        
        for end in range(start,len(s)):
            sub = s[start:end+1]
            if not ishuiwen(sub):
                continue
            path.append(sub)
            dfs(end+1)
            path.pop()
            
    dfs(0)
    return ans

看起来，挺像每个位置依次去试，保证能覆盖所有字串。（下一个从end+1开始查）。从 start 位置开始，枚举下一刀切在哪里。如果 s[start+1] 是回文，就把这一段加入 path，然后递归处理 i+1 后面的部分。当 start == len(s)，说明整个字符串切完了，得到一个合法方案。

如果只用二重循环，得到的是"局部合法片段"，只有dfs到底，才能得到全局合法方案。

LC93 - 复原IP地址#

这题同样是切分问题，判断每个数字是否在0-255之间，在的话才能加入列表，然后用.连接加入答案即可。

Python3 点击展开代码

24 lines 展开代码

    path = []
    ans = []

    def dfs(start: int):
        if len(path) == 4:
            if start == len(s):
                ans.append(".".join(path))
            return

        for end in range(start, min(start + 3, len(s))):
            sub = s[start:end + 1]

            if len(sub) > 1 and sub[0] == "0":
                break

            if int(sub) > 255:
                break

            path.append(sub)
            dfs(end + 1)
            path.pop()

    dfs(0)
    return ans

但是其实细看代码，还是有许多需要注意的逻辑点。首先，我们长度控制在三位及以内，我们应该将这个条件写在end循环中比较好；另外直接转为int，可能会有前导0问题，所以遇到前导0多位数的情况就可以不用继续往后判断了，直接删掉break。

棋盘问题#

LC51 - N皇后#

N皇后也是在试验每个皇后能放在哪，最终能放完所有皇后。但是与之前相比，变成了二维实验。

当然，由于每一行最多只能放一个皇后，所以不用二重循环，用dfs(row)表示给第row行放皇后即可。

一个典型的想法是维持visited数组，每次回溯。但是这样会更复杂一些，不如另一种方法优雅：我们直接用坐标关系，来判断是不是一个竖行、正对角线、副对角线，然后用集合来判断某竖、正负对角是否被用过即可。

Python3 点击展开代码

35 lines 展开代码

def solveNQueens(n: int) -> list[list[str]]:
    ans = []
    board = [["."] * n for _ in range(n)]

    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col

    def dfs(row: int):
        if row == n:
            ans.append(["".join(r) for r in board])
            return

        for col in range(n):
            if col in cols:
                continue
            if row - col in diag1:
                continue
            if row + col in diag2:
                continue

            board[row][col] = "Q"
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            dfs(row + 1)

            board[row][col] = "."
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    dfs(0)
    return ans

LC52 - N皇后II#

N皇后2只要统计解决方案的个数即可，正好可以再练一次手。

Python3 点击展开代码

25 lines 展开代码

def totalNQueens(self, n: int) -> int:
    cols = set()
    diag1 = set()
    diag2 = set()
    count = 0
    def dfs(row):
        nonlocal count
        if row == n:
            count += 1
        for col in range(n):
            if row-col in diag1:
                continue
            if row+col in diag2:
                continue
            if col in cols:
                continue
            diag1.add(row-col)
            diag2.add(row+col)
            cols.add(col)
            dfs(row+1)
            diag1.remove(row-col)
            diag2.remove(row+col)
            cols.remove(col)
    dfs(0)
    return count

LC37 - 解数独#

和上一题类似，我们用两个集合，rows字典和cols字典。我们可以先将所有需要填写的位置用一个数组存起来，然后再dfs去填写：

Python3 点击展开代码

49 lines 展开代码

def solveSudoku(self, board: list[list[str]]) -> None:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    # 先找出所有空位，然后dfs去填
    spaces = []

    for i in range(9):
        for j in range(9):
            if board[i][j] == ".":
                spaces.append((i, j))
            else:
                num = board[i][j]
                rows[i].add(num)
                cols[j].add(num)
                # 还有3x3也要去重合
                boxes[(i // 3) * 3 + j // 3].add(num)

    def dfs(idx: int) -> bool:
        if idx == len(spaces):
            return True

        i, j = spaces[idx]
        box_idx = (i // 3) * 3 + j // 3

        for num in map(str, range(1, 10)):
            if num in rows[i]:
                continue
            if num in cols[j]:
                continue
            if num in boxes[box_idx]:
                continue

            board[i][j] = num
            rows[i].add(num)
            cols[j].add(num)
            boxes[box_idx].add(num)

            if dfs(idx + 1):
                return True

            board[i][j] = "."
            rows[i].remove(num)
            cols[j].remove(num)
            boxes[box_idx].remove(num)

        return False

    dfs(0)

搜索路径问题#

LC79 - 单词搜索#

搜索类问题通常需要向多个方向进行dfs，如果能搜到底就成立。单词搜索的开头不固定，所以我们就二重循环定起点，然后开始dfs。

Python3 点击展开代码

37 lines 展开代码

def exist(self, board: list[list[str]], word: str) -> bool:
    m, n = len(board), len(board[0])
    # dfs(i,j,k)表示当前在ij，要匹配word[k]开始的后缀
    def dfs(i: int, j: int, k: int) -> bool:
        # 特别注意dfs的返回
        # 越界返回
        if i < 0 or i >= m or j < 0 or j >= n:
            return False
        # 非需要字母返回
        if board[i][j] != word[k]:
            return False
        # 长度达标返回True
        if k == len(word) - 1:
            return True

        # 标记，防止重复使用
        ch = board[i][j]
        board[i][j] = "#"

        found = (
            dfs(i - 1, j, k + 1)
            or dfs(i + 1, j, k + 1)
            or dfs(i, j - 1, k + 1)
            or dfs(i, j + 1, k + 1)
        )

        board[i][j] = ch
        return found

    # 多起点dfs
    # 本题不需要path，匹配完成就是满足的
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True

    return False

LC200 - 岛屿数量#

进入dfs的入口写在外面，dfs的次数就代表联通区域：

Python3 点击展开代码

27 lines 展开代码

def numIslands(self, grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    ans = 0

    def dfs(i: int, j: int) -> None:
        # 走到水里或越界
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
            return

        # dfs各种走四个方向
        grid[i][j] = "0"
        dfs(i - 1, j)
        dfs(i + 1, j)
        dfs(i, j - 1)
        dfs(i, j + 1)

    # 找到一块陆地，就dfs把附近的路都水淹掉（标记为0）
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                ans += 1
                dfs(i, j)

    return ans

LC695 - 岛屿的最大面积#

求面积要将所有方向的dfs都加起来，然后在求岛模版上加一个最大面积判断即可。

Python3 点击展开代码

29 lines 展开代码

def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])

    def dfs(i: int, j: int) -> int:
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
            return 0

        grid[i][j] = 0

        # 几个方向都走到头
        return (
            1
            + dfs(i - 1, j)
            + dfs(i + 1, j)
            + dfs(i, j - 1)
            + dfs(i, j + 1)
        )

    max_area = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                max_area = max(max_area, dfs(i, j))

    return max_area

LC130 - 被围绕的区域#

这题也是多源 DFS，但思路要反过来。不要从每个 O 出发判断它是否被 X 包围，而是从边界上的 O 出发，把所有与边界连通的 O 标记为安全。因为只要一个 O 能连到边界，它所在的整个连通块就不能被翻转。最后遍历全图，仍然是 O 的位置说明无法连到边界，改成 X；被标记过的安全位置再改回 O。

Python3 点击展开代码

35 lines 展开代码

def solve(self, board: list[list[str]]) -> None:
    if not board or not board[0]:
        return

    m, n = len(board), len(board[0])

    def dfs(i: int, j: int) -> None:
        if i < 0 or i >= m or j < 0 or j >= n:
            return
        if board[i][j] != "O":
            return

        board[i][j] = "#"

        dfs(i - 1, j)
        dfs(i + 1, j)
        dfs(i, j - 1)
        dfs(i, j + 1)

    # 从边界 O 出发，标记所有安全 O
    for i in range(m):
        dfs(i, 0)
        dfs(i, n - 1)

    for j in range(n):
        dfs(0, j)
        dfs(m - 1, j)

    # 没被标记的 O 是被包围的；# 是安全的
    for i in range(m):
        for j in range(n):
            if board[i][j] == "O":
                board[i][j] = "X"
            elif board[i][j] == "#":
                board[i][j] = "O"

dp的结果就从起点开始一直到终止条件，但是上面几题你可以看出来dp的设计很灵活，需要仔细体会。

LC417 - 太平洋大西洋水流问题#

分桶与划分问题#

LC698 - 划分为K个相等的子集#

这一题和数组连续划分的区别在于，这一题要考虑任意子集划分，所以要使用的方法是分桶划分。

Python3 点击展开代码

38 lines 展开代码

def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
    total = sum(nums)

    if total % k != 0:
        return False

    target = total // k
    nums.sort(reverse=True)

    if nums[0] > target:
        return False

    buckets = [0] * k

    def dfs(index: int) -> bool:
        if index == len(nums):
            return all(bucket == target for bucket in buckets)

        num = nums[index]

        for i in range(k):
            if buckets[i] + num > target:
                continue

            buckets[i] += num

            if dfs(index + 1):
                return True

            buckets[i] -= num

            # 如果当前数字放进空桶都失败了，放进其他空桶也等价
            if buckets[i] == 0:
                return False

        return False

    return dfs(0)

这个思想也很直接，我们从0号桶开始放，放不下了尝试后面的。如果都能放满，就返回True，否则这个方案就不行。剪枝点在于空桶都放不下的话，那直接False。

另外桶划分中，最好让失败趁早发生，也就是说，我们用快排，先把最长的元素塞进桶，早失败早退出。

LC473 - 火柴拼正方形#

写了上一题就知道，这一题实际上还是四桶问题。可以直接写写看。

Python3 点击展开代码

34 lines 展开代码

def makesquare(self, matchsticks: list[int]) -> bool:
    matchsticks.sort(reverse=True)
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    target = total // 4
    buckets = [0] * 4

    # idx是火柴下标
    def dfs(idx):
        if idx == len(matchsticks):
            return all(bucket == target for bucket in buckets)
        matchstick = matchsticks[idx]

        # 遍历桶
        for i in range(4):
            # 放不下就下一个
            if buckets[i] + matchstick > target:
                continue

            # 放进去，就递归，如果递归到底返回True，这里就返回True
            buckets[i] += matchstick
            if dfs(idx + 1):
                return True

            # 回溯
            buckets[i] -= matchstick

            # 剪枝
            if buckets[i] == 0:
                return False
        return False    
        
    return dfs(0)

状态递归：递归函数表示一个状态#

斐波那契与爬楼梯#

LC509 - 斐波那契数#

斐波那切数和爬楼梯应该是很多人动态规划开始的地方。所以我们在这里也写一下dp的方案。

Python3 点击展开代码

9 lines 展开代码

def fib(self, n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

其实，dp就是打表的递归问题，从而避免计算重复问题。会写dp，自然也会写递归：dp初始状态就是递归出口，状态转移公式就是递归函数，直接变化如下：

Python3 点击展开代码

6 lines 展开代码

def fib(self, n: int) -> int:
    def dfs(n):
        if n <= 1:
            return n
        return dfs(n-1) + dfs(n-2)
    return dfs(n)

递归解法由于会重复计算，效率小于dp。为了不进行裸递归，我们可以使用python的缓存装饰器@cache，从而自动进行记忆化搜索。

Python3 点击展开代码

7 lines 展开代码

def fib(self, n: int) -> int:
    @cache
    def dfs(n):
        if n <= 1:
            return n
        return dfs(n-1) + dfs(n-2)
    return dfs(n)

LC70 - 爬楼梯#

跟斐波那契几乎一样。

Python3 点击展开代码

9 lines 展开代码

from functools import cache

def climbStairs(self, n: int) -> int:
    @cache
    def dfs(n):
        if n <= 2:
            return n
        return dfs(n-1)+dfs(n-2)
    return dfs(n)

LC746 - 使用最小花费爬楼梯#

和上一题类似，但是这题是看上楼梯的价值。我们尝试递归。

Python3 点击展开代码

10 lines 展开代码

from functools import cache

def minCostClimbingStairs(self, cost: list[int]) -> int:
    # dfs表示到达下标n的最小费用
    @cache
    def dfs(n):
        if n <= 1:
            return 0
        return min(dfs(n-2)+cost[n-2],dfs(n-1)+cost[n-1])
    return dfs(len(cost))

dp写法如下：

Python3 点击展开代码

6 lines 展开代码

def minCostClimbingStairs(self, cost: list[int]) -> int:
    n = len(cost)
    dp = [0] * (n+1)
    for i in range(2,n+1):
        dp[i] = min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
    return dp[n]

关键在于，这题上完所有楼梯之后还要登顶，等跳出所有楼梯再结算而不是上到最后一级台阶。

网格路径#

LC62 - 不同路径#

这类题目，同样最先想到的是二维dp，是二维dp的启蒙题。

Python3 点击展开代码

13 lines 展开代码

def uniquePaths(self, m: int, n: int) -> int:
    dp = [[1]*n for _ in range(m)]
    # 只能向右或向下，初始化边界
    for i in range(1,m):
        dp[i][0] = 1
    for j in range(1,n):
        dp[0][j] = 1

    for i in range(1,m):
        for j in range(1,n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

dp的题本质上是记忆化递归，所以肯定也能写成递归形式。

Python3 点击展开代码

9 lines 展开代码

from functools import cache

def uniquePaths(self, m: int, n: int) -> int:
    @cache
    def dfs(i,j):
        if i == 0 or j == 0:
            return 1
        return dfs(i-1,j) + dfs(i,j-1)
    return dfs(m-1,n-1)

LC63 - 不同路径II#

与不同路径对比，多了一个障碍物的设计，路径不能从障碍物来，同样也不能到障碍物。

Python3 点击展开代码

26 lines 展开代码

def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    # 这里要用0，因为不是全网格都默认1，所以还要初始化起点
    dp = [[0]*n for _ in range(m)]
    # 起点或终点本身是石头，无路可走
    if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
            return 0
    dp[0][0] = 1
    # 只能向右或向下，初始化边界
    for i in range(1,m):
        # 遇到障碍物直接此路不通
        if obstacleGrid[i][0] == 1:
            break
        dp[i][0] = 1
    for j in range(1,n):
        if obstacleGrid[0][j] == 1:
            break
        dp[0][j] = 1

    for i in range(1,m):
        for j in range(1,n):
            if obstacleGrid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

效率一样的情况下，这一题记忆递归效率更高，注意递归的时候要先判断下标越界再访问下标。

Python3 点击展开代码

15 lines 展开代码

from functools import cache

def uniquePathsWithObstacles(self, obstacleGrid: list[list[int]]) -> int:
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    @cache
    def dfs(i,j):
        if i < 0 or j < 0:
            return 0
        if obstacleGrid[i][j] == 1:
            return 0
        if i == 0 and j == 0:
            return 1
        return dfs(i-1,j) + dfs(i,j-1)
    return dfs(m-1,n-1)

LC64 - 最小路径和#

同样往下或者往右走，我们用 dfs(i,j) 来求解位置i、j的最大小路径。

Python3 点击展开代码

11 lines 展开代码

from functools import cache

def minPathSum(self, grid: list[list[int]]) -> int:
    @cache
    def dfs(i,j):
        if i<0 or j<0 :
            return float('inf')
        if i == 0 and j == 0:
            return grid[0][0]
        return grid[i][j] + min(dfs(i-1,j),dfs(i,j-1))
    return dfs(len(grid)-1,len(grid[0])-1)

代码更简洁，但是要注意花费应该什么时候被计算，这是很重要的，跟收费楼梯又是不一样的逻辑，还有就是越界到底应该怎么返回、传入的下标。这些都是容易爆的地方。

背包递归#

0-1背包#

完全背包#

LC416 - 分割等和子集#

分割成K个子集，是多桶问题，而这里的分割成两个等和子集，其实就是找出是不是有等于和一半的子集，可以将其理解为0-1背包，每个元素选或不选，最终能否达到target。

Python3 点击展开代码

24 lines 展开代码

from functools import cache

def canPartition(self, nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    target = total // 2
    
    # 将状态作为参数传入：i 表示当前下标，curr_sum 表示当前的累加和
    @cache
    def dfs(i, curr_sum):
        # 1. 成功条件：凑齐了！
        if curr_sum == target:
            return True
            
        # 2. 失败/终止条件：超重了，或者所有的数字都选完了
        if curr_sum > target or i == len(nums):
            return False
            
        # 3. 状态转移：选当前数字 OR 不选当前数字
        return dfs(i + 1, curr_sum + nums[i]) or dfs(i + 1, curr_sum)
        
    return dfs(0, 0)

一开始用nonlocal来做curr_sum，实际上可以直接写在函数体内。然后就是第一次写用了nonlocal的flag，来表示有没有找到，这样没办法及时剪枝，从而报了TLE。我们需要用dfs来判断当前位置、当前和开始，能不能找到和为target的划分 ，用一个or连接，失败的条件是target或i超限，这是最好最干净的思路。

LC494 - 目标和#

其实就是用dfs判断每一位是加还是减。

Python3 点击展开代码

11 lines 展开代码

from functools import cache

def findTargetSumWays(self, nums: list[int], target: int) -> int:
    @cache
    def dfs(i,total):
        if i == len(nums) and total == target:
            return 1
        if i == len(nums):
            return 0
        return dfs(i+1,total-nums[i]) + dfs(i+1,total+nums[i])
    return dfs(0,0)

字符串递归#

LC72 - 编辑距离#

本题是经典的二维dp题，我们用dp(i,j)表示处理到了word1/2的位置（前面已经相等），但是有三种操作，分别是插入、删除、替换。删除之前需要i-1对上j，所以对应的操作是 dp[i-1][j] + 1；插入需要j-1位置对应上i，也就是 dp[i][j-1] + 1；替换需要i-1和j-1都对应上，也就是操作数 dp[i-1][j-1] + 1。我们取三者中的最小值，就能解决了。

Python3 点击展开代码

21 lines 展开代码

def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数
    dp = [[0] * (n+1) for _ in range(m+1)]
    # 基础情况
    for i in range(1,m+1):
        dp[i][0] = i
    for j in range(1,n+1):
        dp[0][j] = j

    for i in range(1,m+1):
        for j in range(1,n+1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    dp[i-1][j] + 1,
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1
                )
    return dp[m][n]

本题用dp比较好想。

LC1143 - 最长公共子序列#

我们在一维中经常做到这样的题目，现在要求两个字符串的最长公共子序列，我们依旧可以直接二维dp。

Python3 点击展开代码

14 lines 展开代码

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    # dp[i][j]为text1第i位和text2第j位的最长公共子串。转移方法是当text1[i]和text2[j]相等的时候，dp[i][j] = dp[i-1][j-1] + 1
    m = len(text1)
    n = len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            # Case1、字母相同，直接加到公共子序列
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # 如果不相等，看看谁前进一格能让dp更大
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]

递归解法：

Python3 点击展开代码

12 lines 展开代码

from functools import cache

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    # 递归写法
    @cache
    def dfs(i,j):
        if i < 0 or j < 0 :
            return 0
        if text1[i] == text2[j]:
            return dfs(i-1,j-1)+1
        return max(dfs(i-1,j),dfs(i,j-1))
    return dfs(len(text1)-1,len(text2)-1)

LC115 - 不同的子序列#

子序列问题，判断s子序列中出现t的个数。我们可以直接对s进行dfs，判断符合条件的子序列：

Python3 点击展开代码

23 lines 展开代码

def numDistinct(s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    path = []
    count = 0
    # 用dfs(i)表示第i位选不选，得到t的方案个数
    def dfs(i):
        nonlocal count
        if len(path) == n and "".join(path) == t:
            count += 1
            return
        if i == m:
            return
        # 选
        path.append(s[i])
        dfs(i+1)
        path.pop()

        # 不选
        dfs(i+1)

    dfs(0)
    return count

然而，无脑dfs，必然超时了。这一题其实也是二维dp做法，加一个cache。我们可以将 dp[i][j] 定义为 s 从下标 i 开始的子串，能够匹配出多少个 t 从下标 j 开始的子串。

现在，我们来思考一下转移，这种问题我们要只考虑一个字母。首先，如果两个字母对上了，即 s[i] == t[j]，那么我们有两种选择，要么直接从这开始匹配，dp[i][j] = dp[i+1][j+1]，要么还是不选他，因为后面可能还有，所以是 dp[i][j] = dp[i][j+1]。至于不匹配，那就直接 dp[i][j] = dp[i+1][j+1]。（不过填表的过程需要你用当前dp看之前的dp，写成减号）。

我们来试试按照递归的思路来做，从最后一位开始看。逻辑和上述一样，初始状态是j回退到了0则为1，然后s回退到0即为0

Python3 点击展开代码

16 lines 展开代码

from functools import cache

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        @cache
        def dfs(i,j):
            if j < 0: 
                return 1
            if i < 0:
                return 0
            if s[i] == t[j]:
                return dfs(i-1,j-1) + dfs(i-1,j)
            else:
                return dfs(i-1,j)
    
        return dfs(len(s)-1,len(t)-1)

LC10 - 正则表达式匹配#

本题依旧是基于双指针的dp或者记忆化搜索。基础的规则，如果遇到相同的元素，我们 dp[i][j] = dp[i+1][j+1] ，这是很容易想到的。但是这一题多了.和*。

Python3 点击展开代码

38 lines 展开代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        # dp[i][j] 表示 s 的前 i 个字符，和 p 的前 j 个字符是否匹配
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        
        # Base Case 1：两个空字符串，完美匹配
        dp[0][0] = True
        
        # Base Case 2：s 是空字符串，p 不是空字符串。
        # 只有当 p 是类似 "a*b*c*" 这种可以全部“消除”成空串的结构时，才能匹配
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # 如果遇到星号，它的状态等同于把前面那个字符也一起消除掉之前的状态
                dp[0][j] = dp[0][j-2]
                
        # 正向填表
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 情况 1：普通字符或者 '.'，直接看上一个状态
                if s[i-1] == p[j-1] or p[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                
                # 情况 2：遇到星号
                elif p[j-1] == '*':
                    # 动作 A：消除器（把 p 的末尾字符和 * 一起当空气）
                    # 状态继承自 dp[i][j-2]
                    erase = dp[i][j-2]
                    
                    # 动作 B：克隆器（前提：s 的最后一个字符必须和 p 中星号前面的字符匹配）
                    # 如果匹配，状态继承自 dp[i-1][j] (客人走了一个，规则还在)
                    clone = False
                    if s[i-1] == p[j-2] or p[j-2] == '.':
                        clone = dp[i-1][j]
                        
                    dp[i][j] = erase or clone
                    
        return dp[m][n]

简单来说，待匹配元素为0来初始化dp表，然后.是一定放行，*分为两种情况，消除前面一位或者让前面一位一直重复。

博弈递归#

LC486 - 预测赢家#

从现在我们进入了博弈论 DP（Minimax 极小化极大算法），看代码的时候经常很难理解，因为这套递归中，隐藏了无缝的"视角切换"。之前的题，dfs主视角永远是自己、当前，而博弈论中，dfs变成一个高级模型，两人会轮流使用它得出自己的最优解。

我们只用dfs关心自己的分减去对手分的正负，也就是自己的优势。打个比方，我方选择left的时候，对手采用最优解得到的相对我的分数是 dfs(left+1,right)，那么我想对于对手的最优解得到的分数增加就是 nums[left] - dfs(left+1, right)。

所以，实际上我们在两种选择，都会考虑相对于对手的最优解我们的最优解，最终只要判断从这过区间开始，第一个开始选的人能不能让优势大于0，就可以解决这题了。

Python3 点击展开代码

17 lines 展开代码

from functools import cache

def PredictTheWinner(self, nums: list[int]) -> bool:
    @cache
    def dfs(left: int, right: int) -> int:
        # 只剩一个可以拿
        if left == right:
            return nums[left]

        # dfs(left, right) 表示在区间 [left, right] 中，当前玩家相对于对手最多能领先多少分。
        take_left = nums[left] - dfs(left + 1, right)
        take_right = nums[right] - dfs(left, right - 1)

        return max(take_left, take_right)

    # 对手的优势大于0就输了
    return dfs(0, len(nums) - 1) >= 0

LC877 - 石子游戏#

这一题其实跟预测赢家一样，我们用dfs来表示对手可能产生的优势，按照相同方式求解。

Python3 点击展开代码

14 lines 展开代码

from functools import cache

def stoneGame(self, piles: list[int]) -> bool:
    @cache
    def dfs(i,j):
        if i == j:
            return piles[i]
        
        take_left = piles[i] - dfs(i+1,j)
        take_right = piles[j] - dfs(i,j-1)

        return max(take_left,take_right)
    
    return dfs(0,len(piles)-1)  > 0

不过，这一题可以直接用石子游戏题目结论秒杀，结论就是先手必胜。。直接return True。

构造递归：递归地生成答案#

生成括号#

LC22 - 括号生成#

dfs生成答案的过程中，我们还要保证括号有效，所以我们需要left和right来维持有效性，可以用nonlocal更改或者直接当参数传入。

Python3 点击展开代码

21 lines 展开代码

def generateParenthesis(self, n: int) -> list[str]:
    ans = []
    path = []

    def dfs(left: int, right: int):
        if len(path) == 2 * n:
            ans.append("".join(path))
            return

        if left < n:
            path.append("(")
            dfs(left + 1, right)
            path.pop()

        if right < left:
            path.append(")")
            dfs(left, right + 1)
            path.pop()

    dfs(0, 0)
    return ans

构造二叉树#

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

树是天然递归结构，我用左右指针对准dfs的结果就行，dfs定义为完成构建的二叉树。同时，我们传入目前的前序和中序数组。

Python3 点击展开代码

14 lines 展开代码

def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode:
    if not preorder or not inorder:
        return None

    root_val = preorder[0]
    root = TreeNode(root_val)

    idx = inorder.index(root_val)
    left_size = idx

    root.left = self.buildTree(preorder[1:1 + left_size], inorder[:idx])
    root.right = self.buildTree(preorder[1 + left_size:], inorder[idx + 1:])

    return root

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

跟上一题如出一辙，我们记得按照方式划分即可。

Python3 点击展开代码

16 lines 展开代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.left = left
        self.right = right
        self.val = val

def buildTree(self, inorder: list[int], postorder: list[int]) -> TreeNode:
    # 后序左右根，中序左根右
    if not postorder:
        return None
    root = TreeNode(postorder[-1])
    # 左侧长度为idx
    idx = inorder.index(postorder[-1])
    root.left = buildTree(inorder[:idx],postorder[:idx])
    root.right = buildTree(inorder[idx+1:],postorder[idx:-1])
    return root

LC654 - 最大二叉树#

这一题直接就把构造的过程告诉你了，照猫画虎即可。

Python3 点击展开代码

9 lines 展开代码

def constructMaximumBinaryTree(self, nums: list[int]) -> TreeNode:
    if len(nums) == 0:
        return None
    max_num = max(nums)
    root = TreeNode(max_num)
    idx = nums.index(max_num)
    root.left = constructMaximumBinaryTree(nums[:idx])
    root.right = constructMaximumBinaryTree(nums[idx+1:])
    return root

LC108 - 将有序数组转换为二叉搜索树#

既然已经是有序数组了，我们每次取中间部分即可。和前面的题没啥区别：

Python3 点击展开代码

8 lines 展开代码

def sortedArrayToBST(self, nums: list[int]) -> TreeNode:
    if not nums:
        return None
    mid = len(nums)//2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    return root

序列化与反序列化#

LC297 - 二叉树的序列化与反序列化#

这一题其实可以通过特判空的bfs来解决，这也是带null数组建树的过程和逆过程，我们来实操一下。

Python3 点击展开代码

47 lines 展开代码

from collections import deque

class Codec:
    def serialize(self, root):
        if not root:
            return ""

        q = deque([root])
        ans = []

        while q:
            node = q.popleft()

            if not node:
                ans.append("null")
                continue

            ans.append(str(node.val))
            q.append(node.left)
            q.append(node.right)

        return ",".join(ans)

    def deserialize(self, data):
        if not data:
            return None

        vals = data.split(",")
        root = TreeNode(int(vals[0]))
        q = deque([root])
        # 反序列化需要用i指导位置，然后按照左右左右添加即可。
        i = 1

        while q:
            node = q.popleft()

            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                q.append(node.left)
            i += 1

            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                q.append(node.right)
            i += 1

        return root

但是既然放在这里，那就说明可以通过递归构造法来构造。实际上，我们只要先序遍历就能得到树的，虽然顺序不一样，但是序列化本来就是布置一种顺序，所以用dfs也是可以的。

Python3 点击展开代码

34 lines 展开代码

class Codec:
    def serialize(self, root):
        vals = []

        def dfs(node):
            if not node:
                vals.append("null")
                return

            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(vals)

    def deserialize(self, data):
        vals = data.split(",")
        self.i = 0

        def dfs():
            if vals[self.i] == "null":
                self.i += 1
                return None

            node = TreeNode(int(vals[self.i]))
            self.i += 1

            node.left = dfs()
            node.right = dfs()

            return node

        return dfs()

LC449 - 序列化和反序列化二叉搜索树#

有左小右大规律，可以靠值范围恢复结构。这样，我们就不需要null了，直接按照前序建立。然后，反序列化的过程，用BST的上界和下界值域约束：

Python3 点击展开代码

36 lines 展开代码

class Codec:
    def serialize(self, root):
        vals = []

        def dfs(node):
            if not node:
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(vals)

    def deserialize(self, data):
        if not data:
            return None

        vals = list(map(int, data.split(",")))
        self.i = 0

        def dfs(lower, upper):
            if self.i == len(vals):
                return None

            val = vals[self.i]
            if val < lower or val > upper:
                return None

            self.i += 1
            node = TreeNode(val)
            node.left = dfs(lower, val)
            node.right = dfs(val, upper)
            return node

        return dfs(float("-inf"), float("inf"))

数学递归：按公式定义问题#

阶乘#

经典递归入门。

Python3 点击展开代码

7 lines 展开代码

def solution(n:int):
    @cache
    def dfs(n:int):
        if n<=1:
            return 1
        return dfs(n-1)*n 
    return dfs(n)

最大公约数#

正常做法是从1找到一半（或者平方根）能整除n的数。最大公约数最经典的递归算法是欧几里得算法，核心结论是 gcd(a, b) = gcd(b, a % b) 。所以我们辗转相除，最终一定能得到结果：

Python3 点击展开代码

5 lines 展开代码

def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    if b == 0:
        return a
    return gcd(b, a % b)

快速幂#

本来x的n次幂要乘n次，时间复杂度是On。但是如果我们存中间的过程，每次把问题减半，就会降低复杂度到Onlogn

Python3 点击展开代码

16 lines 展开代码

def myPow(x: float, n: int) -> float:
    def dfs(n: int) -> float:
        if n == 0:
            return 1

        half = dfs(n // 2)

        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

    if n >= 0:
        return dfs(n)
    else:
        return 1 / dfs(-n)

面试题 08.06. 汉诺塔问题#

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

汉诺塔问题也非常经典

这题是递归最经典的数学模型之一。移动 n 个盘子，看起来很复杂，但如果把最大的盘子单独拿出来看，事情就清楚了：

1
1. 先把上面的 n-1 个盘子借助目标柱移到辅助柱
2
2. 再把最大的那个盘子移到目标柱
3
3. 最后把辅助柱上的 n-1 个盘子借助起始柱移到目标柱

也就是说，汉诺塔的本质是：

1
移动 n 个盘子 = 先解决 n-1 个盘子 + 移动最大的盘子 + 再解决 n-1 个盘子

递归出口就是只剩一个盘子时，直接移动即可：

Python3 点击展开代码

8 lines 展开代码

def hanoi(n: int, source: str, auxiliary: str, target: str) -> None:
    if n == 1:
        print(f"{source} -> {target}")
        return

    hanoi(n - 1, source, target, auxiliary)
    print(f"{source} -> {target}")
    hanoi(n - 1, auxiliary, source, target)

本题最少移动次数是 2^n - 1，时间复杂度为 O(2^n)，空间复杂度为递归栈深度 O(n)。它特别适合帮助理解"把大问题拆成相同形式的小问题"这件事。

约瑟夫环#

卡特兰数#

递归优化#

记忆化搜索#

记忆化搜索，就是在递归的基础上加一个缓存，把已经算过的状态保存起来，避免重复计算。

它最适合这种场景：

1
递归状态很多次重复出现。

典型比如斐波那契数列，朴素递归会反复计算 f(n-1)、f(n-2)。加上记忆化之后，就能把指数级复杂度压下来。

一个常见模板：

Python3 点击展开代码

7 lines 展开代码

from functools import cache

@cache
def dfs(state):
    if 递归出口:
        return base
    return 由更小状态转移得到的结果

记忆化搜索本质上就是"自顶向下的动态规划"。

尾递归#

尾递归指的是：递归调用是函数中的最后一步，当前层在递归返回后不再做额外运算。

比如下面这种就更接近尾递归：

Python3 点击展开代码

4 lines 展开代码

def dfs(n, acc):
    if n == 0:
        return acc
    return dfs(n - 1, acc + n)

不过在 Python 里，尾递归并不会像某些语言那样自动优化掉栈空间，所以更多是一个概念上的了解，不用特别执着去写尾递归风格。

剪枝#

剪枝就是：发现当前这条递归分支不可能成为答案时，提前停掉，不再继续往下搜。

常见剪枝方式有：

超过目标值直接返回，比如组合总和
同层重复元素直接跳过，比如子集II、组合总和II、全排列II
当前状态已经不合法，立即返回，比如括号生成、N皇后
当前最优值已经不可能超过已有答案，直接停掉

回溯题很多时候能不能通过，差别就在剪枝是否及时。

递归转迭代#

递归本质上是系统帮我们维护调用栈，所以很多递归都能改写成"显式维护栈"的迭代。

最常见的例子就是树遍历：

Python3 点击展开代码

4 lines 展开代码

stack = [root]
while stack:
    node = stack.pop()
    ...

一般来说：

如果题目天然是树、图、回溯结构，递归通常更直观
如果数据规模很大，担心爆栈，或者逻辑本身就是线性的，迭代通常更稳

能不能从递归切到迭代，本质上就是看你能不能把"当前层还没做完的信息"自己存在栈里。

递归爆栈问题#

当递归层数太深时，就会爆栈。最常见的情况有：

链表递归，但链表很长
树退化成链表
DFS 图/网格时搜索深度过大
递归出口写错，导致无限递归

所以写递归题时，要特别注意：

出口是否一定能到
每次递归规模是否真的变小
最坏情况下递归深度是多少

Python递归深度限制#

Python 默认递归深度不高，通常在千级左右。刷题时，如果递归层数可能达到几万，就要警惕。

有时候可以临时调整：

Python3 代码示例

2 lines

import sys
sys.setrecursionlimit(10**6)

但这不是万能解法。真正更稳的方式还是：

改迭代
优化递归结构
减少不必要的深度

递归题目的分类判断#

看数据结构#

如果题目本身给的是链表、树、图、网格，那么先想递归往往没错，因为这些结构天然具有"一个部分里还嵌着更小的同类部分"的特点。

链表：当前节点 + 后续链表
二叉树：当前节点 + 左右子树
网格/图：当前点 + 四周可达状态

看是否可以拆成子问题#

如果一个问题能自然地写成：

1
当前问题 = 更小规模的同类问题 + 当前层处理

那它大概率就能用递归。

比如：

反转链表：反转后续链表，再接回当前节点
Pow(x, n)：先求 x^(n//2)，再平方
汉诺塔：先移动 n-1 个盘子，再移动最大的

看是否需要枚举选择#

如果每一步都有多个选择，而你需要把所有可能都试一遍，那通常就是回溯递归。

比如：

子集：选或不选
组合：下一个选哪个数
排列：当前位置放谁
N皇后：当前行放哪一列

看是否存在重复子问题#

如果不同路径会反复进入同一个状态，那就不要只写朴素递归了，应该进一步考虑记忆化搜索。

比如：

斐波那契
爬楼梯
编辑距离
预测赢家

这些题如果只递归不缓存，复杂度通常会很难看。

看是否需要回溯撤销选择#

如果你在递归过程中修改了某些状态，并且回到上一层后还要恢复原状，那这就是典型回溯。

比如：

path.append(...) 之后要 path.pop()
棋盘上放皇后后，回来要撤销
数独填数字后，回来要删掉
网格搜索里标记访问后，回来要恢复

递归常见模板#

链表递归模板#

链表递归常见于"返回处理后的链表头"：

Python3 点击展开代码

10 lines 展开代码

def dfs(head):
    if not head or not head.next:
        return head

    new_head = dfs(head.next)

    # 当前层处理指针关系
    ...

    return new_head

这类题要特别注意：改指针之前，先想清楚当前层到底返回什么。

二叉树递归模板#

二叉树递归最常见的是后序汇总：

Python3 点击展开代码

8 lines 展开代码

def dfs(root):
    if not root:
        return base

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

    return 用 left 和 right 合并当前答案

如果题目需要自顶向下传信息，也可以写成前序：

Python3 点击展开代码

7 lines 展开代码

def dfs(root, state):
    if not root:
        return

    # 先处理当前节点
    dfs(root.left, new_state)
    dfs(root.right, new_state)

分治递归模板#

分治递归就是"先拆，再治，最后合并"：

Python3 点击展开代码

9 lines 展开代码

def dfs(left, right):
    if left == right:
        return 单点答案

    mid = (left + right) // 2
    left_info = dfs(left, mid)
    right_info = dfs(mid + 1, right)

    return merge(left_info, right_info)

如果题目涉及跨中点答案，就把"跨中点"也写在 merge 里考虑进去。

回溯递归模板#

组合、排列、切割、棋盘题大多长这样：

Python3 点击展开代码

15 lines 展开代码

ans = []
path = []

def dfs(start):
    if 达成答案:
        ans.append(path[:])
        return

    for i in range(start, 范围终点):
        if 当前选择不合法:
            continue

        path.append(选择)
        dfs(下一层状态)
        path.pop()

如果是排列问题，通常没有 start，而是用 used 数组控制。

记忆化搜索模板#

Python3 点击展开代码

8 lines 展开代码

from functools import cache

@cache
def dfs(state1, state2):
    if 递归出口:
        return base

    return 根据更小状态计算结果

一旦题目有"区间 + 最优策略""字符串前缀 + 最优值""当前位置 + 剩余容量"这类重复状态，都可以先想这个模板。

DFS网格搜索模板#

Python3 点击展开代码

10 lines 展开代码

def dfs(i, j):
    if 越界或当前位置不合法:
        return

    标记当前位置已访问

    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)

如果题目要求统计面积、路径数、是否可达，就把 return 的值改成对应的量即可。

递归问题总结#

递归专题走到这里，最重要的其实不是记住多少题，而是形成几个稳定的直觉。

第一，先定义函数，不要先写代码。

1
这个递归函数到底返回什么？
2
它处理的是哪个子结构、哪个区间、哪个状态？

第二，出口一定要和函数定义匹配。

1
空节点返回什么？
2
空区间返回什么？
3
目标达成时返回什么？

第三，很多递归题真正难的不是"怎么递"，而是"怎么归"。

普通树题往往递下去不难，真正要想清楚的是：

回来的时候要汇总什么信息
是否要维护全局答案
是否需要在当前层做合并

第四，回溯题的关键不是会不会写 path.append() 和 path.pop()，而是：

1
这一层的选择范围是什么？
2
什么情况该 continue？
3
什么情况该 break？
4
哪些状态要撤销？

第五，分治题不要先急着看代码，先问：

1
左边返回什么？
2
右边返回什么？
3
当前层怎么合并？

最后给自己留一个非常实用的判断口诀：

1
树和链表，先想结构递归；
2
要试所有可能，先想回溯；
3
问题能切两半，先想分治；
4
状态重复出现，先想记忆化；
5
网格四向扩散，先想 DFS。

递归不是一类题，而是一种看问题的方式。只要能把"当前问题"写成"更小的同类问题 + 当前层处理"，递归就自然出来了。