09_动态规划

经典题型

五、区间 DP

状态为 dp[i][j] 表示区间 [i, j] 的最优解。遍历顺序：区间长度从小到大。

LC 516. 最长回文子序列

516. 最长回文子序列（中等）

给定一个字符串，找到其中最长的回文子序列的长度（子序列不要求连续）。

1. 状态：dp[i][j] = s[i..j] 中最长回文子序列的长度
2. 转移：
   • s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2 （首尾配对，中间取最优）
   • 否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1]) （丢弃左端或右端）
3. 初始化：dp[i][i] = 1
4. 遍历：i 从 n-1 到 0，j 从 i+1 到 n-1
5. 返回：dp[0][n-1]

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

三、字符串 DP

LC 1143. 最长公共子序列

1143. 最长公共子序列（中等）

给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。

1. 状态定义：dp[i][j] = text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度
2. 转移方程：
   • 如果 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
   • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 初始化：全部为 0
4. 遍历：从上到下、从左到右
5. 返回：dp[m][n]

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), 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):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

五、区间 DP 与树形 DP（进阶）

区间 DP

区间 DP 处理的是”在一个区间上做决策”的问题，状态一般定义为 dp[i][j] 表示区间 [i, j] 的最优解。

遍历顺序的关键：区间长度从小到大，先处理短区间，再处理长区间。

戳气球（LC 312）

https://leetcode.cn/problems/burst-balloons/

有 n 个气球，编号 0 到 n-1，每个气球上标有一个数字。戳破气球 i 可以获得 nums[left] * nums[i] * nums[right] 个硬币。求能获得的最大硬币数。

关键技巧：在数组两端各添加一个值为 1 的虚拟气球，然后思考”哪个气球最后被戳破”（而不是先戳哪个），这样戳破第 k 个气球时，左右两侧已经是独立的子问题了。

五步法分析：

1. 状态定义：dp[i][j] = 戳破开区间 (i, j) 内所有气球能获得的最大硬币数
2. 转移方程：枚举区间内最后戳破的气球 k dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，其中 i < k < j
3. 初始化：dp[i][j] = 0（区间内没有气球时，硬币数为 0）
4. 遍历顺序：区间长度从 2 到 n+1（因为两端有虚拟气球）
5. 返回值：dp[0][n+1]（0 和 n+1 是虚拟气球）

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        # 两端添加虚拟气球
        nums = [1] + nums + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        
        for i in range(n - 1, -1, -1):          # 区间左端点，从下往上
            for j in range(i + 2, n + 2):       # 区间右端点，从左往右
                for k in range(i + 1, j):       # 枚举最后戳破的气球 k
                    dp[i][j] = max(dp[i][j],
                                   dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
        return dp[0][n + 1]

经典题目清单

入门级

题号	题目	核心思路
LC 70	爬楼梯	斐波那契递推
LC 509	斐波那契数	最基础的 DP
LC 746	使用最小花费爬楼梯	爬楼梯变体

基础级

题号	题目	核心思路
LC 53	最大子数组和	线性 DP
LC 198	打家劫舍	选或不选
LC 62	不同路径	网格 DP
LC 64	最小路径和	网格 DP
LC 322	零钱兑换	完全背包

进阶级

题号	题目	核心思路
LC 416	分割等和子集	0-1 背包
LC 1143	最长公共子序列	字符串 DP
LC 72	编辑距离	字符串 DP
LC 300	最长递增子序列	线性 DP + 二分优化
LC 516	最长回文子序列	区间 DP
LC 312	戳气球	区间 DP
LC 337	打家劫舍 III	树形 DP
LC 543	二叉树的直径	树形 DP

---

小结

动态规划的核心就是两件事：状态定义和状态转移方程。

推荐的学习路径：

1. 先写暴力递归：不考虑效率，用递归把问题解出来
2. 加记忆化：在递归基础上加一个缓存（字典或数组），消除重复计算
3. 改写为 DP 表：把自顶向下的递归改成自底向上的循环
4. 空间优化：如果 dp[i] 只依赖 dp[i-1]，就可以用滚动变量代替整个数组

暴力递归 → 记忆化搜索 → DP 表 → 空间优化

记住：DP 题目做多了自然就有感觉了。每道题都用五步法分析，刻意练习，很快就能在面试中游刃有余。

---

模板速查

以下为常用 DP 模板的浓缩版（背包 / 计数 / LIS / LCS / 编辑距离 / 区间 DP），复习时快速过一遍：

动态规划

# ===== 1. 背包问题 =====
# 01 背包（每个物品选0或1次）
def knapsack_01(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # 倒序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 完全背包（每个物品可选无限次）
def knapsack_complete(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # 正序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 多重背包（每个物品可选有限次）- 二进制优化
def knapsack_multi(n, W, weights, values, counts):
    items = []  # 转化为01背包
    for i in range(n):
        k = 1
        c = counts[i]
        while c > 0:
            take = min(k, c)
            items.append((weights[i] * take, values[i] * take))
            c -= take
            k *= 2
    dp = [0] * (W + 1)
    for w, v in items:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

# ===== 计数DP（爬楼梯/骰子问题）=====
# 每次可以走1~k步，求到达n级台阶的走法数
def count_ways(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1  # 基础情况：到达0级只有1种方式（不走）
    for i in range(1, n + 1):
        dp[i] = sum(dp[max(0, i-k):i]) % MOD
    return dp[n]

# 简化为：每次走1~6步（骰子问题）
dp = [1]
for i in range(int(input())):
    dp.append(sum(dp[-6:]) % MOD)
print(dp[-1])

# ===== 2. 最长上升子序列 (LIS) =====
def lis(arr):
    import bisect
    dp = []
    for x in arr:
        pos = bisect.bisect_left(dp, x)
        if pos == len(dp):
            dp.append(x)
        else:
            dp[pos] = x
    return len(dp)

# ===== 3. 最长公共子序列 (LCS) =====
def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

# ===== 4. 编辑距离 =====
def edit_distance(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = i
    for j in range(m+1):
        dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

# ===== 5. 区间 DP =====
def interval_dp(n, cost):
    # dp[i][j] = 合并 i~j 的最小代价
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]