算法与数据结构：动态规划 5 大解题模板

动态规划是算法面试中区分度最高的题型，核心思想是把大问题拆为重叠子问题、存储中间结果避免重复计算。掌握通用五步法加五类高频模板，90%的 DP 题都能解。

通用五步法与背包类

五步：① 状态定义 dp[i][j] 含义 ② 转移方程（找最后一步两种选择）③ 初始化 base case ④ 遍历顺序 ⑤ 滚动数组空间优化。01 背包每个物品选/不选，容量倒序；完全背包物品可多次选，容量正序。

from functools import lru_cache
from typing import List
import bisect

def t1_01_knapsack(cap: int, ws: List[int], vs: List[int]) -> int:
    n = len(ws); dp = [0] * (cap + 1)
    for i in range(n):
        for c in range(cap, ws[i] - 1, -1):
            dp[c] = max(dp[c], dp[c - ws[i]] + vs[i])
    return dp[cap]

def t2_unbounded_knapsack(cap: int, ws: List[int], vs: List[int]) -> int:
    dp = [0] * (cap + 1)
    for c in range(1, cap + 1):
        for i, w in enumerate(ws):
            if w <= c: dp[c] = max(dp[c], dp[c - w] + vs[i])
    return dp[cap]

def t3_lcs(a: str, b: str) -> int:
    m, n = len(a), len(b); prev = [0] * (n + 1)
    for i in range(1, m + 1):
        cur = [0] * (n + 1)
        for j in range(1, n + 1):
            cur[j] = prev[j - 1] + 1 if a[i - 1] == b[j - 1] else max(prev[j], cur[j - 1])
        prev = cur
    return prev[n]

def t4_lis(nums: List[int]) -> int:
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

def t5_interval_palindrome_cuts(s: str) -> int:
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = s[i] == s[j] and (j - i < 3 or is_pal[i + 1][j - 1])
    cut = [float('inf')] * n
    for j in range(n):
        if is_pal[0][j]: cut[j] = 0
        else:
            for i in range(1, j + 1):
                if is_pal[i][j]: cut[j] = min(cut[j], cut[i - 1] + 1)
    return int(cut[n - 1])

if __name__ == "__main__":
    print(t1_01_knapsack(10, [2, 3, 5, 7], [3, 4, 6, 10]))
    print(t3_lcs("abcde", "aceb"), t4_lis([10, 9, 2, 5, 3, 7, 101, 18]))
    print(t5_interval_palindrome_cuts("aabcbdadcb"))

子序列 / 区间 / 状压 / 树形

子序列类通常两串用二维 dp[i][j]。区间 DP 按区间长度枚举，适合回文/博弈/合并石子。状态压缩用 bitmask 表示访问过的点集（TSP）。树形 DFS 对每个子节点返回(选/不选)两状态。

最佳实践

写不出转移方程时先暴力搜索+记忆化，画出递归树就能看到重叠子问题的形状，再转自底向上迭代就清晰了。先过样例再空间优化。