二叉树经典问题
1. 什么是满二叉树、完全二叉树、完美二叉树、二叉搜索树和平衡二叉树？
这是树结构里最容易混在一起的五类二叉树概念，先把定义、特征和例子拆开看。
🌳 1. 满二叉树（Full Binary Tree）
✅ 定义：
每个非叶子节点都有且只有两个子节点（左、右各一个）。
❌ 注意：
- 不要求所有叶子节点在同一层。
- 但没有“只有一个子节点”的节点。
🌰 例子：
A
/ \
B C
/ \ / \
D E F G
这是满二叉树，每个非叶子节点都有两个子节点。
🌳 2. 完全二叉树（Complete Binary Tree）
✅ 定义：
一棵有 n 个节点 的二叉树：
- 从上到下、从左到右填满（层序编号连续）。
- 只允许最底层节点右侧缺失，不能左边缺失。
🌰 例子：
A
/ \
B C
/ \ /
D E F
- 节点 F 没有右兄弟，但没问题。
- 如果 F 在右边而 E 缺失，就不是完全二叉树。
🌳 3. 完美二叉树（Perfect Binary Tree）
✅ 定义：
满足两个条件：
- 所有非叶子节点都有两个子节点（即满二叉树）；
- 所有叶子节点都在同一层。
所以「完美二叉树 = 满二叉树 + 叶子在同一层」
🌰 例子：
A
/ \
B C
/ \ / \
D E F G
这个是完美二叉树（也是满的），因为所有叶子都在第3层。
🌳 4. 二叉搜索树（BST，Binary Search Tree）
✅ 定义：
对任意一个节点：
- 左子树上所有节点值 小于 当前节点；
- 右子树上所有节点值 大于 当前节点；
- 中序遍历是升序排列。
🌰 例子：
8
/ \
4 10
/ \ \
2 6 12
中序遍历：2 → 4 → 6 → 8 → 10 → 12，是升序的。
🌳 5. 平衡二叉树（AVL 树）
✅ 定义：
一种高度平衡的二叉搜索树（BST），要求：
- 任意节点左、右子树的高度差 不超过 1。
🌰 例子：
5
/ \
3 7
/ /
2 6
每个节点左右子树高度差不超过 1，是平衡的。
✅ 总结对比表
| 类型 | 特点 |
|---|---|
| 满二叉树 | 所有非叶子节点都有两个子节点 |
| 完全二叉树 | 除最后一层外都满，最底层从左到右连续填充 |
| 完美二叉树 | 满二叉树 + 所有叶子节点在同一层 |
| 二叉搜索树 | 左 < 根 < 右，适用于快速查找 |
| 平衡二叉树 | BST + 每个节点左右子树高度差 ≤ 1 |
2. 给定节点总数 $n$ ，完全二叉树可能的最小高度是多少？
高度（从 1 开始）为 $h$ 的完美二叉树有 $2^h-1$ 个节点。高度为 $h$ 的完全二叉树，节点数量 $n$ 满足 $2^{h-1}\le n\le 2^h-1$ 。给定节点数量 $n$ ，找到第一个满足 $2^h-1 \ge n$ 的 $h$ ，就得到最小高度 $h_{min}=\lceil\log_2(n+1)\rceil$ 。
3. 给定节点总数 $n$ ，这有可能是一棵满二叉树吗？
满二叉树的节点数量 $n=2*h-1$ ，所以只需要判断 $n+1$ 是否为偶数即可。
4. 二叉搜索树的前驱后继怎么找（迭代实现）？
前驱可以用迭代方式找：
class TreeNode:
def __init__(self, val=0, parent=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
self.parent = parent
def find_preprocessor(root, val):
cur = self.root
# 找到val的位置
while cur and cur.val != val:
if val < cur.val:
cur = cur.left
else:
cur = cur.right
if not cur:
return None
if cur.left:
# 如果存在左子树，那么前驱就是左子树的最右节点
cur = cur.left
while cur.right:
cur = cur.right
return cur
# 否则一直往上走，直到 cur != cur.parent.left
pa = cur.parent
while pa and pa.left != cur:
cur = pa
pa = cur.parent
return pa
5. 二叉搜索树的怎么删除一个节点？
二叉搜索树的删除比查找麻烦一些，分三种情况：
- 删除的节点是叶子节点，直接删除即可。
- 删除的节点只有一个子节点，直接将子节点替换到删除节点的位置即可。
- 删除的节点有两个子节点，需要找到这个节点右子树中的最小节点，将这个节点的值替换到删除节点的位置，再删除这个最小节点。
参考代码：
def tranplant(root, u, v):
# 移植子树 v 到 u 的位置，并且调整关系
if u.parent is None:
root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
if v:
v.parent = u.parent
def delete(root, val):
cur = root
# 找到 cur 的位置
while cur and cur.val != val:
if val < cur.val:
cur = cur.left
else:
cur = cur.right
if not cur:
return None
if cur.left is None:
tranplant(root, cur, cur.right)
elif cur.right is None:
tranplant(root, cur, cur.left)
else:
y = cur.right
while y.left:
y = y.left
if y.parent != cur:
tranplant(root, y, y.right)
y.right = cur.right
y.right.parent = y
tranplant(root, cur, y)
y.left = cur.left
y.left.parent = y
6. 结点数量为 $n$ 的二叉树，有多少种不同的结构？
不同的二叉树结构会对应不同的递归顺序（出栈和入栈）。令 $1$ 表示进栈， $0$ 表示出栈，可转化为求一个 $2n$ 位、含 $n$ 个 $1$、 $n$ 个 $0$ 的二进制数，并且从左往右扫描到任意一位时，经过的 $0$ 数不多于 $1$ 数。含 $n$ 个 $1$ 、 $n$ 个 $0$ 的 $2n$ 位二进制数共有 $\binom{2n}{n}$ 个，接着扣掉不满足要求的部分。
假设某个不合法序列在位置 $2m+1$ 处首次违规，此时 $0$ 的数量恰好比 $1$ 多一位，后半段中 $1$ 的数量必然比 $0$ 多一位。具体而言， $0$ 有 $n-m-1$ 位， $1$ 有 $n-m$ 位。把 $2m+2$ 及之后的序列反转，即可得到一个包含 $n+1$ 个 $0$、 $n-1$ 个 $1$ 的序列。这个构造是双射：一个不合法序列会得到唯一的 $n+1$ 个 $0$、 $n-1$ 个 $1$ 的序列，反过来也唯一对应一个不合法序列。
定义映射 $f$ ：从不满足条件的 $n$ 个 $1$ 和 $n$ 个 $0$ 的序列到 $n+1$ 个 $0$ 和 $n-1$ 个 $1$ 的序列。 映射 $f$ 的构造：找到第一个违反条件的位置（称为关键位置）将此位置之后的所有 $0$ 变 $1$ ， $1$ 变 $0$ 。
证明 $f$ 是单射（一对一）：
假设两个不同的不满足条件的序列 A 和 B 映射到同一个序列
- A 和 B 的关键位置必然相同（否则映射结果会不同）
- 如果 A 和 B 在关键位置之前有任何不同，映射后仍然不同
- 如果 A 和 B 在关键位置之后有任何不同，由于0和1互换，映射后仍然不同
因此，不可能有两个不同的序列映射到同一个序列。
证明 $f$ 是满射（映上）：
对于任何 $n+1$ 个 $0$ 和 $n-1$ 个 $1$ 的序列 $S$ ，从左到右扫描，必然存在一个位置， $0$ 的数量比 $1$ 的数量多2（因为总共多2个0）。这个位置就是我们寻找的关键位置， 将此位置之后的 $0$ 和 $1$ 互换，得到一个 $n$ 个 $1$ 和 $n$ 个 $0$ 的序列 $T$。 $T$ 在关键位置之前满足条件，在关键位置不满足条件，因此 $T$ 是一个不满足原条件的序列，且 $f(T) = S$ 。
证明 $f$ 的逆映射：
对于任何 $n+1$ 个 $0$ 和 $n-1$ 个 $1$ 的序列，找到 $0$ 比 $1$ 多2的位置（一定存在且唯一）。将此位置之后的 $0$ 和 $1$ 互换，这个过程是上述映射的逆过程。
证毕。
所以合法的序列（也就是二叉树不同结构数量）等于：
$$ \binom{2n}{n} - \binom{2n}{n+1} $$也就是卡特兰数，其实卡特兰数还满足以下的性质：
$$ C_0 = 1, C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} $$$C_i$ 可以看成是左子树的数量， $C_{n-i}$ 可以看成是右子树的数量，根据乘法原理即可得到总的数量。
数组经典问题（双指针、滑动窗口、二分）
1. 二分查找如何实现？开区间写法、闭区间写法？
二分查找是在有序数组中高效查找的基础算法，也可以推广到单调（非严格、严格）函数上，也就是算法模板里常见的二分答案。关键点不是模板本身，而是证明答案确实有某种单调性。
二分的思想很简单，写法却有不少边界细节。这里按区间开闭拆成三种常见实现。
闭区间写法最常见，核心形式为 $l \le r \le n$ ，其中 $l$ 和 $r$ 分别为左右边界， $n$ 为数组长度。
我们可以定义一个函数 $f(x)$ ，如果 $f(x)$ 为真，则 $x$ 属于右侧合法区间，否则 $x$ 属于不合法区间。
如果区间中点 $mid=(l+r)/2$ 满足 $f(mid)$ ，更新 $r=mid-1$ ，否则更新 $l=mid+1$ 。
基于这个写法，可以观察到两个循环不变量： $[0,l)$ 都是非法的， $(r,n-1]$ 都是合法的，而 $[l,r]$ 是待确定区间。循环结束时， $l$ 或者 $r+1$ 就是答案。
# 举一个例子，我们寻找有序数组中第一个大于等于 target 的位置
# f(x) = nums[x] >= target
def lower_bound(nums, target):
n = len(nums)
l, r = 0, n-1
while l <= r: # 保证区间不为空
mid = (l+r)//2
if nums[mid] >= target:
r = mid-1
else:
l = mid+1
return l
沿着这个闭区间写法，可以推导出等价的开区间写法和左闭右开写法。
对于开区间，循环不变量是 $[0,l]$ 都是非法的， $[r,n-1]$ 都是合法的，中间的 $(l,r)$ 是待确定区间。
# 开区间写法
def lower_bound(nums, target):
n = len(nums)
l, r = -1, n # 注意这里 l, r 的取值范围, l = l-1, r = r+1
while l+1 < r:
mid = (l+r)//2
if nums[mid] >= target:
r = mid
else:
l = mid
return r
对于左闭右开区间，循环不变量变成 $[0,l)$ 是非法的， $[r,n-1]$ 都是合法的，中间的 $[l,r)$ 是待确定区间。
# 左闭右开写法
def lower_bound(nums, target):
n = len(nums)
l, r = 0, n
while l < r:
mid = (l+r)//2
if nums[mid] >= target:
r = mid
else:
l = mid+1
return l # l == r
2. 滑动窗口算法与二分答案算法
题目：假设有一个长度为 $n$ 的非负整数的数组，我们需要找到其中和不大于 $sum$ 的最长子数组的长度。
这题是滑动窗口和二分答案都能处理的典型例子。先看二分答案。
非负整数子数组的和会随长度增加而保持不减，不会因为扩展长度反而变小。假设已经找到了一个长度为 $L$ 的合法子数组，那么长度介于 $[0,L)$ 的合法子数组也能找到，因为不断缩短即可。因此答案具有单调性，可以用二分加速寻找。
# 使用二分答案算法
def get_longgest_subarray(nums, sum):
n = len(nums)
pre = [0] * (n+1)
for i in range(1, n+1):
pre[i] = pre[i-1] + nums[i-1]
def check(val) -> bool:
# 检查是否存在一个长度为val的合法子数组
nonlocal pre
for i in range(1, n-val+2):
# [i, i+val-1]
if pre[i+val-1] - pre[i-1] <= sum:
return True
return False
l, r = -1, n+1 # 开区间写法
while l+1 < r:
mid = (l+r)//2
if check(mid):
l = mid
else:
r = mid
return l # 根据循环不变量 [0,l] 是合法的
从二分答案继续往前推，会发现最长子数组其实可以动态维护。比如对于以 $nums[i]$ 结尾的子数组，已知它的最远左边界为 $left$ ；那么以 $nums[i+1]$ 结尾时，最远左边界不会跑到 $left$ 左侧。因为前面已经推导过，长度越长，子数组和保持不减。这一点可以用反证法证明，这里不展开。于是可以用两个指针维护当前最大长度，也就是经典滑动窗口。
# 双指针（滑动窗口）
def get_longgest_subarray(nums, sum):
n = len(nums)
l, s = 0, 0
ans = 0
for i in range(n):
s += nums[i]
while s > sum:
s -= nums[l]
l += 1
if i - l + 1 > ans:
ans = i - l + 1
return ans
二分答案经常用来解决一种答案具有单调性质的问题，而根据计算复杂度理论，检查是否成立比求解简单。而滑动窗口算法则是一种全局的优化，本质上是动态规划的思想。二分答案在面试算法题中是一种非常重要的算法。
回溯算法经典问题
回溯算法通过穷举所有可能解来求解问题，常见于组合、排列、棋盘和字符串切分等题目。面试里也很爱考，因为它看起来是在搜索，本质上却很吃建模。思考这类题目时，可以按这三步拆：
- 确定搜索的空间。
- 确定搜索的策略。
- 确定搜索的终止条件。
枚举子集
定义：给定一个集合，求出其所有子集（或者统计其信息）。
子集问题的核心在于每个元素都有两种状态：要么被选入当前子集，要么不被选入。因此，子集问题的规模为 $2^n$ ，即每个元素的选择组合。
练习题目1：17. 电话号码的字母组合
分析一下题目，我们对于其中的每一个数字按键都有多种选择，形式上如果我们知道了按键长度，是可以使用迭代方法获取所有方案的，但是由于我们不知道按键的长度，这个时候就需要回溯算法来实现动态的搜索。
choice = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
n = len(digits)
ans = []
cur = [''] * n
if n == 0:
return ans
def dfs(i):
if i == n: # 确定好终止条件，这是很重要的，防止无限递归
ans.append(''.join(cur))
return
for num in choice[int(digits[i])]:
cur[i] = num
dfs(i+1)
dfs(0)
return ans
练习题目2：78. 子集
对于每一个数字我们可以选或者不选，因为每一个元素都是不相同的，所以这保证了所有方案的独立性，不需要去重。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
cur = []
def dfs(i):
if i == n:
ans.append(cur.copy())
return
# 选择
cur.append(nums[i])
dfs(i+1)
# 回溯
cur.pop()
# 不选择
dfs(i+1)
dfs(0)
return ans
练习题目3：131. 分割回文串
回溯思路是：对每一个位置尝试切或不切；如果切出来的片段不是回文串，直接剪枝。
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
ans = []
cur = []
def dfs(i):
if i == n:
ans.append(cur.copy())
return
for j in range(i,n):
t = s[i:j+1]
if t == t[::-1]: # 判断回文串
cur.append(t)
dfs(j+1)
cur.pop()
dfs(0)
return ans
解决组合问题
定义：从给定的元素中选取一定数量的元素，求出所有可能的组合。
组合问题的核心在于，每次选择后，前面的元素不能再被重新选择，且每个组合的顺序不影响结果。这是它和排列问题最关键的区别。
练习题目1：77. 组合
这道题是典型组合问题：在子集问题的基础上增加选择次数限制。利用这些限制，可以给原本简单的搜索策略加一些启发式规则，也就是剪枝。
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
cur = []
def dfs(i):
if len(cur) == k:
ans.append(cur.copy())
return
# 剪枝, [i,n] 还有 n-i+1个数字
if n-i+1 < k-len(cur):
return
for j in range(i,n+1):
cur.append(j)
dfs(j+1)
cur.pop()
dfs(1)
return ans
练习题目2：216. 组合总和 III
这道题和练习题目 1 很像，只是多了一个限制：最后选择的元素和要等于指定数字。这个限制可以直接放进搜索策略里，再配合对应的剪枝，提高搜索效率。
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
ans = []
cur = []
s = 0 # 当前和
def dfs(i):
nonlocal s
# 剪枝1, [i,n], 个数限制
if n-i+1 < k-len(cur):
return
# 剪枝2, i,i+1,i+2...n, 数字和限制
if (n+i)*(n-i+1)//2 < n-s or s > n:
return
if len(cur)==k and s == n:
ans.append(cur.copy())
return
for j in range(i,10):
cur.append(j)
s += j
dfs(j+1)
s -= j
cur.pop()
dfs(1)
return ans
解决排列问题
定义：从给定的元素中选取一定数量的元素，使得元素间满足一定的顺序，求出所有可能的排列。
排列问题和组合问题的最大区别在于，排列问题需要考虑元素间的顺序，而组合问题只需要考虑元素是否被选择。
练习题目1：46. 全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
cur = []
def dfs(s):
if s == 0:
ans.append(cur.copy())
return
for j in range(n):
if s & (1<<j):
cur.append(nums[j])
dfs(s ^ (1<<j))
cur.pop()
dfs((1<<n)-1)
return ans
这里使用了二进制集合的方法表示了当前的选择的数字以及还没有选择的数字，比如数字nums[i]就对应了 $s$ 中的第 $i$ 位，0表示已经选择了，否则就表示还没有选择。
练习题目2：51. N 皇后
此题的难点在于检查皇后是否处于同一行、同一列、同一对角线上。我们可以将对角线进行一个哈希编码，从而用于快速判断在某条对角线上是否存在皇后。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
board = ["." * n for _ in range(n)]
if n == 0:
return ans
column = [False] * n
ldiag = [False] * (2 * n - 1) # 左对角线
rdiag = [False] * (2 * n - 1) # 右对角线
def backtrack(row):
if row == n:
ans.append(board.copy())
return
for col in range(n):
# 计算左对角线和右对角线的索引
l_diag_index = row - col + (n - 1)
r_diag_index = row + col
# 检查当前位置是否被攻击
if column[col] or ldiag[l_diag_index] or rdiag[r_diag_index]:
continue
# 放置皇后
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
column[col] = ldiag[l_diag_index] = rdiag[r_diag_index] = True
# 递归到下一行
backtrack(row + 1)
# 移除皇后（回溯）
board[row] = board[row][:col] + '.' + board[row][col+1:]
column[col] = ldiag[l_diag_index] = rdiag[r_diag_index] = False
backtrack(0)
return ans
动态规划经典问题
背包问题
背包问题是一类经典动态规划问题，变形很多。一般面试里，重点掌握 01 背包和完全背包即可。
01 背包和完全背包与前面的回溯思想很像，都是围绕选还是不选做规划。动态规划题目没有太多捷径，得靠练习把状态定义和转移练熟。
01 背包
1. 问题描述
给定 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的费用为 $C_i$ ，价值为 $W_i$ 。每种物品只能选择一次，问如何选择物品使得总价值最大，且总费用不超过背包容量。
2. 动态规划求解
状态定义: 设 $F[i][v]$ 表示前 $i$ 件物品放入容量为 $v$ 的背包时的最大价值。
状态转移方程:
$$F[i][v] = \max(F[i-1][v], F[i-1][v-C_i] + W_i)$$优化空间复杂度: 可以使用一维数组 $F[v]$ ，并采用逆序遍历来避免覆盖问题。
3. 基础 Python 代码模板
def knapsack_01(weights, values, V):
n = len(weights)
dp = [0] * (V + 1)
for i in range(n):
for v in range(V, weights[i] - 1, -1):
dp[v] = max(dp[v], dp[v - weights[i]] + values[i])
return dp[V]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
V = 8
max_value = knapsack_01(weights, values, V)
print(f"01背包问题的最大价值为: {max_value}")
完全背包问题
1. 问题描述
与 01 背包不同，每种物品可以选择无限次。仍给定 $N$ 件物品和一个容量为 $V$ 的背包，求在总费用不超过背包容量的情况下，如何选择物品使得总价值最大。
2. 动态规划求解
- 状态定义: 设 $F[v]$ 表示容量为 $v$ 的背包可以获得的最大价值。
- 状态转移方程: $$F[v] = \max(F[v], F[v - C_i] + W_i)$$
- 算法优化: 采用顺序遍历更新 $F[v]$ ，以允许同一物品多次选择。
3. 基础 Python 代码模板
def knapsack_complete(weights, values, V):
n = len(weights)
dp = [0] * (V + 1)
for i in range(n):
for v in range(weights[i], V + 1):
dp[v] = max(dp[v], dp[v - weights[i]] + values[i])
return dp[V]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
V = 8
max_value = knapsack_complete(weights, values, V)
print(f"完全背包问题的最大价值为: {max_value}")
递推顺序的问题
可以发现， 01 背包和完全背包的实现代码很像，主要区别在第二层循环的容量枚举顺序。01 背包中，枚举顺序是逆序；完全背包中，枚举顺序是顺序。
为什么这样可行？01 背包限定每种物品只能选 1 次，逆序更新是为了先更新大容量的 dp 值，保证当前容量的 dp 值只依赖上一轮状态。
在完全背包中，每种物品可以被选取任意次，因此在更新 $F[v]$ 时，需要使用可能已经包含当前物品的状态。顺序遍历 $v$ 可以确保 $F[v - C_i]$ 已经包含了当前物品 $i$ 的选取情况。
更具体地说，如果按从 $C_i$ 到 $V$ 的顺序遍历， $F[v]$ 的更新过程相当于在考虑“再选一次第 $i$ 种物品”。这种更新方式允许我们在已经选取若干次当前物品的基础上再次选取，从而得到正确解。
练习题目
1、目标和
对于每一个数字，可以选择使用它的正数或者负数。形式上，可以把不同数字放到两个堆里，相当于是 01 选择。假设正数和为 $sp$ ，负数的绝对值和为 $sn$ ，就有：
$$ sp - sn = target $$由于 $sp + sn = s$ ， $s$ 是数组的和，就可以得到：
$$ \begin{align} s - sn - sn &= target \\ s - target &= 2 * sn \\ \end{align} $$因此可以得到 $sn = (s-target)/2$ ，这是固定值。问题就转成了：从一堆数字中选取若干个，使其和恰好为 $sn$ ，求方案数。这是经典 01 背包题目。
参考代码：
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums) - target
if s < 0 or s % 2 != 0:
return 0
sn = s // 2
# 01 knapsack
n = len(nums)
dp = [0] * (sn + 1)
dp[0] = 1
for i in range(n):
for j in range(sn, nums[i]-1, -1):
dp[j] += dp[j-nums[i]]
return dp[sn]
2、分割等和子集
此题和上面的题目非常类似，读者可以自己体会。
参考代码：
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2 != 0:
return False
s //= 2
n = len(nums)
dp = [0] * (s + 1)
dp[0] = 1
for i in range(n):
for j in range(s, nums[i]-1, -1):
dp[j] |= dp[j-nums[i]]
if j == s and dp[j]:
return True
return False
这道题里的 dp 值只包含 0 或 1，所以可以用 bitset 优化。对于位置 $j$ 而言，每一次 $dp[j]$ 都只是或上前面 $nums[i]$ 位置上的 $dp[j-nums[i]]$ 。
因此可以把整个数组看成一个 bitset，并行计算所有位置。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 1:
target = total // 2
dp = 1
for num in nums:
dp |= dp << num
return (dp >> target) & 1 == 1
return False
3、零钱兑换 I
本题是典型完全背包问题。
参考代码：
inf = 0x3f3f3f3f
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [inf] * (amount + 1)
dp[0] = 0
for c in coins:
for v in range(c, amount+1):
dp[v] = min(dp[v], dp[v-c]+1)
return dp[amount] if dp[amount] < inf else -1
4、零钱兑换 II
这道题和上题不同，更关注不同方案的数量。它仍然属于完全背包，只是目标函数从最优值变成了计数。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for v in range(c, amount+1):
dp[v] += dp[v-c]
return dp[amount]
区间 DP
区间 DP 是一种特殊的动态规划方法，主要用于解决带区间子结构的线性 DP 问题，严格来说也属于序列 DP。其特点是：
- 状态定义：通常定义 $dp[i][j]$ 表示闭区间 $[i,j]$ 上的最优解
- 区间长度：一般从小区间逐渐扩展到大区间
- 状态转移：通常需要在区间内枚举分割点 $k$
对于区间 DP，有三种很常见的状态转移模式：
- 合并模式： $dp[i][j] = \min/\max(dp[i][k] + dp[k+1][j]) + cost$
- 首尾关联： $dp[i][j] = dp[i+1][j-1] + f(i,j)$
- 区间扩展： $dp[i][j] = dp[i][j-1]$ 或 $dp[i+1][j] + f(i,j)$
其中， $f(i,j)$ 表示了我们需要自定义的处理或者代价函数。
练习题目
1、最长回文子串
这个问题的动态规划转移方程属于第二种常见的区间 DP 转移模式，即 $dp[i][j]$ 的计算依赖于其内部子区间的 DP 值。
具体的转移方程如下：
基本情况 (Base Cases):
- 长度为 1 的子串: 任何单个字符都是回文。所以，对于所有的 $i$， $dp[i][i] = \text{true}$。
- 长度为 2 的子串: 子串 $s[i \dots i+1]$ 是回文当且仅当 $s[i]$ 和 $s[i+1]$ 相等。所以，$dp[i][i+1] = (s[i] == s[i+1])$。
递推关系 (Transition):
- 考虑长度大于 2 的子串 $s[i \dots j]$。它是一个回文子串当且仅当：
- 它的首尾字符相等，即 $s[i] == s[j]$。
- 去掉首尾字符后剩下的子串 $s[i+1 \dots j-1]$ 也是一个回文子串。
- 所以，对于 $j > i+1$（即子串长度大于 2），转移方程为： $$ dp[i][j] = (s[i] == s[j]) \land dp[i+1][j-1] $$ 这里的 $\land$ 表示逻辑与 (AND)。
- 考虑长度大于 2 的子串 $s[i \dots j]$。它是一个回文子串当且仅当：
DP 的计算顺序：
由于 $dp[i][j]$ 依赖于 $dp[i+1][j-1]$（一个更短的子串），需要先计算短子串的 DP 值，再计算长子串。因此，典型计算顺序是按照子串的**长度（length）**从小到大迭代：
- 长度 $L = 1$: 计算所有的 $dp[i][i]$。
- 长度 $L = 2$: 计算所有的 $dp[i][i+1]$。
- 长度 $L = 3, 4, \dots, n$: 对于每个长度 $L$，遍历所有可能的起始索引 $i$（从 0 到 $n-L$），计算 $j = i+L-1$，然后使用转移方程 $dp[i][j] = (s[i] == s[j]) \land dp[i+1][j-1]$ 来计算 $dp[i][j]$。
为什么是“第二种常见模式”？
常见的区间 DP 模式通常有两种：
- 依赖于区间分裂点: $dp[i][j]$ 的计算需要枚举一个分裂点 $k$ ($i \le k < j$)，然后结合 $dp[i][k]$ 和 $dp[k+1][j]$ 的结果。例如，矩阵链乘法、最优二叉搜索树等。
- 依赖于内部子区间: $dp[i][j]$ 的计算依赖于去掉首尾或只去掉一端的子区间的 DP 值，例如 $dp[i+1][j-1]$、$dp[i+1][j]$ 或 $dp[i][j-1]$。最长回文子串（依赖 $dp[i+1][j-1]$）、一些字符串匹配问题（如编辑距离的变种）等属于此类。
最长回文子串的 DP 转移方程 $dp[i][j] = (s[i] == s[j]) \land dp[i+1][j-1]$ 正是依赖于去掉首尾字符后的内部子区间 $s[i+1 \dots j-1]$ 的 DP 值 $dp[i+1][j-1]$，因此符合第二种模式。
在填充完整个 $dp$ 表后，你需要遍历所有的 $dp[i][j]$，找到所有值为 true 的项，并记录其中 $j-i+1$（子串长度）最大的那个子串，它就是最长的回文子串。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * (n+1) for _ in range(m+1)]
dp[1][1] = 1
for i in range(1,m+1):
for j in range(1,n+1):
dp[i][j] += dp[i-1][j] + dp[i][j-1]
return dp[m][n]
3、数字 1 的个数
给定一个整数 $n$ ，计算所有小于等于 $n$ 的非负整数中数字 $1$ 出现的次数。
这道题属于比较复杂的计数 DP，也称数位 DP。这类题通常是在一个具体限制区间里，统计满足某种性质的数字个数。 这种性质通常和数位有关。比如本题，需要统计所有数字中 1 出现的总次数，就是很经典的数位 DP 形式。
通常用记忆化搜索实现数位 DP，而不是手写递推，因为记忆化搜索更灵活，递推实现难度更高。 做记忆化搜索时，可以把过程想象成从高位到低位填数字，通常需要关注这些变量：
is_num，表示当前位置下，前面是否已经填了任何一个大于0的数字。（因为不能包含前导零）is_limit，表示当前位置下，能够填的数字是9还是对应的一个上限。
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n)
# 使用cache装饰器非常方便实现记忆化搜索
@cache
def dfs(p, is_limit, is_num, cnt) -> int:
# p表示当前填数字的位置，cnt表示目前填了多少个1
if p == len(s):
return cnt
up = int(s[p]) if is_limit else 9
res = 0
if not is_num:
res += dfs(p+1, False, False, cnt) # 依然选择不填
# 这里必须要从1开始选择，否则就是包含前导0
for i in range(1,up+1):
res += dfs(p+1, is_limit and i == up, True, cnt + (i == 1))
else:
for i in range(0, up+1):
res += dfs(p+1, is_limit and i == up, True, cnt + (i == 1))
return res
return dfs(0, True, False, 0)
基础数据结构经典问题（链表、队列、栈）
栈
栈是一种后进先出（LIFO）的数据结构，只能在一端（栈顶）操作。主要操作包括：
push: 将元素添加到栈顶pop: 移除栈顶元素peek/top: 查看栈顶元素但不移除
栈常用于递归、表达式求值、括号匹配等场景，也是面试高频内容。它对建模要求偏高，需要把经典题和变式题吃透。这里先看栈的经典应用和单调栈题目。
1、有效的括号
这是一道经典栈题，关键在建模：把左括号看作进栈，右括号看作出栈，那么所有合法括号序列都可以唯一对应一个进出栈操作序列。
class Solution:
def isValid(self, s: str) -> bool:
dic = {'{': '}', '[': ']', '(': ')', '?': '?'}
stack = ['?']
for c in s:
if c in dic:
stack.append(c)
elif dic[stack.pop()] != c:
return False
return len(stack) == 1
Python 没有像 Java、C++ 那样提供专门的栈结构，但可以用列表模拟栈。因为每次都操作列表末尾元素，性能上可以保证。
2、最长有效括号
此题是上题的强化版本，思维难度高了很多。简单来讲，此题需要在不合法的括号序列中找到最长的合法的括号子串，也就意味着找到的合法子串一定也可以唯一对应一个栈的操作序列，由于我们需要找到的是子串，这说明所有合法的括号子串在原来的括号序列中是一段一段的形式。
比方说我们有这个字符串：(()())))()()(()))((())，可以看到其中的合法括号子串有：
(()())()()(())(())
从上面的结果来看，我们首先可以使用一个栈将所有的合法的括号位置标记出来，然后在从左到右遍历即可。
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = []
valid = [False] * len(s)
# 标记有效的括号对
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else: # ')'
if stack and s[stack[-1]] == '(':
valid[stack[-1]] = True
valid[i] = True
stack.pop()
# 计算最长连续有效括号的长度
max_len = 0
current_len = 0
for i in range(len(s)):
if valid[i]:
current_len += 1
else:
max_len = max(max_len, current_len)
current_len = 0
# 不要忘记检查最后一组连续有效括号
max_len = max(max_len, current_len)
return max_len