企业官网建设流程全解析

动态规划这个名字，十个人里有九个第一次听都觉得高深莫测，好像必须得是算法竞赛选手才能碰的东西。但你要是真正上手写过几道题，再回过头看，会发现它本质上就一句话：把大问题拆成小问题，并且记住小问题的答案，避免重复计算。

这篇东西我不会上来就甩一堆术语，而是从"为什么要用动态规划"讲起，用五道经典例题做横向对比，每一道都给出完整可运行的 Python 源码，再聊聊那些题解里很少写清楚、但你在实际写代码时一定会踩到的坑。无论你是刚接触算法的学生，还是工作中需要自己写点策略优化代码的工程师，只要跟着走一遍，动态规划就没那么玄乎了。

1. 动态规划到底在解决什么问题：先搞清楚它的适用边界

很多人学动态规划学得痛苦，不是因为它本身难，而是因为根本没弄明白"什么题该用动态规划"就硬往上套，结果套得四不像。

1.1 从阶乘问题说起：什么是递推关系

先看一个小学就接触过的例子——阶乘。5! = 5 × 4 × 3 × 2 × 1，但你也可以写成5! = 5 × 4!。这里就出现了一个非常关键的关系：要算出 n 的阶乘，只需要先算出 (n-1) 的阶乘。这种"我这个问题的答案，依赖一个规模更小的同类问题的答案"的关系，就叫递推关系。

def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)

这段代码没有任何动态规划的影子，但它包含了动态规划最核心的种子：大问题的答案可以通过小问题的答案推导出来。

1.2 动态规划的三个硬性条件

不是所有能递推的问题都能用动态规划。要真正用动态规划，必须同时满足三个条件，少了任何一个都不行：

• 最优子结构：大问题的最优解，包含小问题的最优解。比如你要求从北京到上海的最短路径，而且这条路经过南京，那么北京到南京这一段，也必须是北京到南京的所有路径中最短的那条。如果不满足这个性质，动态规划就没法用。
• 重叠子问题：大问题拆分出来的小问题，会被反复多次计算。还是拿最短路径举例，从北京到上海，不管走哪条路线，可能都会经过同一个中间城市，那么这个中间城市的最短路径就被重复计算了。动态规划的核心价值就是把这些重复计算的结果存起来，下次直接用。
• 状态转移方程：能用一个数学表达式描述"大问题和小问题之间的关系"。这是整个动态规划的灵魂，后面每一道例题我都会重点拆这个方程是怎么来的。

生活化的类比就是记账。你有记账的习惯，这个月每一笔开销都记下来，月底想算总支出，直接把账本翻一遍加起来就行——账本就是你已经算好的子问题结果，不需要重新回忆每一笔钱花在哪。

1.3 什么时候不该用动态规划

这一点很多人忽略，但我必须说清楚，否则你做题的时候容易走火入魔。遇到以下特征的题目，别硬套动态规划：

• 无重叠子问题：比如快速排序、二分查找，每次拆出来的子问题都是独立的，彼此之间没有重复。这类问题用分治更合适。
• 需要输出具体路径：动态规划擅长求"最优值是多少"，但如果题目要你输出"具体走了哪条路线"，虽然也能做，但通常要在动态规划之外额外维护路径信息，实现成本高不少。
• 状态空间爆炸：有些题目理论上可以用动态规划，但状态数量有几十个维度，空间复杂度高到无法承受。比如有些涉及一堆物品、多种限制条件的组合优化题，这时候往往得另寻出路。

我看过太多人，拿到一个题不管三七二十一先写动态规划，写不出来就说"这题太难了"。其实大概率是压根没用对方法。

2. 一套能复用的思考框架：从暴力递归到动态规划

动态规划不是凭空想出来的，它有一条非常清晰的演进路径：暴力递归 → 记忆化搜索 → 动态规划。我强烈建议你遇到新题的时候，先按照这个顺序走一遍，而不是一上来就盯着状态转移方程憋半天。

2.1 第一步：先写暴力递归

暴力递归的关键是：不要想优化，就按最直白的方式把问题描述成递归。

以经典的斐波那契数列为例，题目要求f(n) = f(n-1) + f(n-2)，其中f(0)=0, f(1)=1。最朴素的写法就是：

def fib_brute(n): if n <= 1: return n return fib_brute(n - 1) + fib_brute(n - 2)

这段代码逻辑完全正确，但跑n=50的时候就会卡到怀疑人生。问题出在哪儿？

你可以画一下递归调用树：算fib(5)需要算fib(4)和fib(3)；算fib(4)又需要算fib(3)和fib(2)。注意看，fib(3)被重复计算了至少两次。当 n 变大，这种重复会呈现指数级爆炸，时间复杂度是 O(2^n)，不是吓唬你，是真的慢到 n=50 就基本跑不完了。

2.2 第二步：加一层"记忆"，变成记忆化搜索

既然问题是重复计算，那就把已经算过的结果存起来。用一个字典（或者数组）当缓存，每次计算前先查一下，查到了直接返回，算不到就存进去：

def fib_memo(n, memo=None): if memo is None: memo = {} if n <= 1: return n if n in memo: return memo[n] memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n]

这个版本的时间复杂度瞬间从 O(2^n) 降到了 O(n)，n=100 也毫无压力。这其实已经抓住动态规划的本质了——用空间换时间。这种"从上往下递归 + 记忆化缓存"的写法，就是记忆化搜索。

2.3 第三步：翻转计算方向，得到标准动态规划

记忆化搜索虽然能解决问题，但递归本身有函数调用开销，而且当递归深度特别大时还有爆栈风险。更好的做法是自底向上：先算f(0)、f(1)，再算f(2)，一步步滚到f(n)。

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

这才是我们常说的动态规划形态。整个过程非常像你在Excel里做公式下拉：每一项都只依赖前面已经算好的行，算完后面就再也不回头看了。至于网上各种优化版本的"只用两个变量滚动更新"，都只是在这个基础上的空间优化，先把标准版本写对再说。

这套"暴力递归 → 记忆化搜索 → 动态规划"的三步走，我后面讲的五道例题，思路全部来自这里。

3. 五道典型例题逐题拆解：状态定义、转移方程、源码对照

说再多理论，不落到具体题目上都是空的。下面这五道题，从易到难排序，每道题都是面试和工程里的常客。我先讲怎么想，再给完整代码，最后说坑在哪。

3.1 爬楼梯：一模一样，又能复习一遍

题目：你正在爬楼梯，每次只能爬 1 阶或 2 阶，问爬到第 n 阶有多少种不同的方法。

这道题和斐波那契几乎一模一样。状态定义：dp[i]表示爬到第 i 阶的方法总数。转移方程：到达第 i 阶，要么是从第 i-1 阶迈 1 步上来的，要么是从第 i-2 阶迈 2 步上来的，所以dp[i] = dp[i-1] + dp[i-2]。边界条件：dp[0]=1（原地不动算一种），dp[1]=1。

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

是不是觉得"这不就是斐波那契换了个皮"？没错。很多动态规划题都是同一个内核换了不同的题目背景。你如果能把这道题直接优化成只维护两个变量，说明对空间优化已经有感觉了：

def climb_stairs_optimized(n): if n <= 1: return 1 prev, cur = 1, 1 for _ in range(2, n + 1): prev, cur = cur, prev + cur return cur

3.2 01背包：动态规划的"扛把子"，必须吃透

题目：有 N 件物品和一个容量为 W 的背包。每件物品有自己的重量w[i]和价值v[i]，问怎么装，能让背包里的总价值最大。

01背包是动态规划里最经典的题型，没有之一。它衍生出的变体题型多到数不清，所以这道题的思路值得花大力气搞清楚。

状态定义：dp[i][j]表示"考虑前 i 件物品，背包容量为 j 时，能获得的最大总价值"。

转移方程是这道题的核心，需要仔细理解。对于第 i 件物品，只有两种选择：

• 不选它：那价值就是dp[i-1][j]，和前 i-1 件物品、容量 j 的情况完全一样。
• 选它：那前提是当前容量j >= w[i]，装进去之后，背包剩余容量是j - w[i]，但你获得了价值v[i]。于是总价值是dp[i-1][j-w[i]] + v[i]。

所以状态转移方程是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 当 j >= w[i] dp[i][j] = dp[i-1][j] 当 j < w[i]

写成代码：

def knapsack_01(weights, values, capacity): n = len(weights) # dp[i][j] 表示前 i 件物品装入容量 j 的背包的最大价值 # 多开一行一列，方便处理 i=0 或 j=0 的边界 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if weights[i - 1] <= j: dp[i][j] = max( dp[i - 1][j], # 不选第 i 件 dp[i - 1][j - weights[i - 1]] + values[i - 1] # 选第 i 件 ) else: dp[i][j] = dp[i - 1][j] # 装不下只能不选 return dp[n][capacity]

跑个测试看看：

weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 5 # 最优选择：第1件(价值3) + 第2件(价值4) = 重量2+3=5，总价值7 print(knapsack_01(weights, values, capacity)) # 输出 7

我能给你的最大建议是：这道题别只背代码，一定要自己动手把二维 dp 表一行一行填一遍。填表的过程你会真正理解"选与不选"两个分支分别对应什么，后面的一维滚动数组优化才看得懂。

3.3 零钱兑换：min版本的背包问题

题目：给定不同面额的硬币coins和一个总金额amount，求凑成总金额所需的最少的硬币个数。每种硬币数量无限。

这道题和01背包对比着看非常有意思。01背包是"每件物品最多选一次"，零钱兑换是"每种硬币可以无限选"。但它们的核心框架完全一致。

状态定义：dp[i]表示凑出金额 i 所需的最少硬币数。

转移方程：凑出金额 i，最后一步一定是用了一枚硬币c，那么凑出i-c再加上这一枚硬币，就是dp[i-c] + 1。我们要在所有可能的硬币面额里挑出最小值：

dp[i] = min(dp[i - c] for c in coins if c <= i) + 1

边界条件：dp[0] = 0。其他金额初始化为一个很大的数，比如float('inf')，表示"还没凑出来"。

def coin_change(coins, amount): # dp[i] 表示凑出金额 i 需要的最少硬币数 dp = [float('inf')] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for c in coins: if c <= i: dp[i] = min(dp[i], dp[i - c] + 1) return dp[amount] if dp[amount] != float('inf') else -1

踩坑提示：很多新手会先把dp数组初始化为-1，然后判断的时候晕头转向。float('inf')在这类"求最小值"的题目里是最好用的初始值，因为它天然参与min比较却不会被选中，最后再统一判断一次是否不可达就好。

coins = [1, 2, 5] amount = 11 print(coin_change(coins, amount)) # 输出 3 (5+5+1)

3.4 最长公共子序列：二维状态，找到"对不上"的情况怎么办

题目：给定两个字符串text1和text2，返回它们的最长公共子序列的长度。子序列不要求连续，但必须保持相对顺序。

这道题是"两个序列"类动态规划的鼻祖，很多字符串匹配问题都是从它衍生出去的。

状态定义：dp[i][j]表示text1的前 i 个字符和text2的前 j 个字符的最长公共子序列长度。

转移方程要分情况讨论：

• 如果text1[i-1] == text2[j-1]，那这两个字符一定可以拼到公共子序列的末尾，所以dp[i][j] = dp[i-1][j-1] + 1。
• 如果两个字符不相等，那当前这个位置至少能继承哪边的结果？可能是text1的前 i-1 个字符和text2的前 j 个字符的结果，也可能是text1的前 i 个字符和text2的前 j-1 个字符的结果，取更大的那个：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 当 text1[i-1] != text2[j-1]

def longest_common_subsequence(text1, text2): 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] print(longest_common_subsequence("abcde", "ace")) # 输出 3

这里有一个特别容易让人困惑的点：为什么text1[i-1]和text2[j-1]不等时，要取max(dp[i-1][j], dp[i][j-1])而不是dp[i-1][j-1]？因为"只退一个序列"和"两个序列各退一格"相比，前者保留了更多的可能性。dp[i-1][j]包含了所有在前 i-1 个字符里能匹配 j 个字符的情况，而dp[i-1][j-1]只是其中一部分，所以从覆盖范围来看，max(dp[i-1][j], dp[i][j-1])一定不小于单纯的dp[i-1][j-1]，直接用这个表达式就没有遗漏。

3.5 最长递增子序列：变体多到数不完的一道题

题目：给定一个无序整数数组，找到其中最长严格递增子序列的长度。

这道题和最长公共子序列名字很像，但状态定义和转移完全不一样，单独拿出来对比学习会特别涨功力。

状态定义：dp[i]表示"以第 i 个元素结尾的最长递增子序列的长度"。注意，不是"前 i 个元素"，而是"必须包含第 i 个元素"。

转移方程：对每一个i，往前面找所有比nums[i]小的nums[j]，那么nums[i]可以拼在nums[j]后面，形成dp[j] + 1的新子序列。取所有可能的最大值：

dp[i] = max(dp[j] + 1 for j in range(i) if nums[j] < nums[i])，初始值为 1

def length_of_lis(nums): if not nums: return 0 n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])) # 输出 4，例如 2,3,7,101

注意一个很容易犯的错：最后返回的是max(dp)而不是dp[n-1]。因为最长递增子序列不一定以最后一个元素结尾，可能在数组中间就已经达到最长了。很多人第一次写这道题，返回dp[-1]导致答案差了，半天排查不出来。

4. 五道题横向对比：状态定义和转移方程放在一起看，规律就藏不住

把上面的五道题放在同一张表里，动态规划的套路会变得非常清晰：

只看这张表，能得出什么结论？

第一，状态定义是最关键的一步。状态定错了，后面的转移方程怎么推都是歪的。"一维还是二维""以谁结尾还是前几个""代表最大值还是最小值"，这些决定会直接影响整个题目的难度。我个人的经验是：先把所有的约束条件、题目问的东西列出来，再考虑用几个变量能把这些条件全覆盖。比如背包问题显然需要物品编号和容量两个维度，所以状态必然是二维的。

第二，转移方程就是"最后一步怎么走"。倒着想：如果我已经知道所有子问题的答案了，那么从"最后一步"往前推，最终答案是怎么合成的？爬楼梯的最后一步是"迈1阶"或"迈2阶"，背包的最后一步是"最后一件物品选还是不选"，零钱兑换的最后一步是"最后用哪枚硬币"。想清楚最后一步，转移方程就写出来了一大半。

第三，空间复杂度的优化空间往往比时间复杂度的优化空间大得多。01背包、爬楼梯、零钱兑换都能优化成一维数组，最长公共子序列可以优化成滚动数组，最大递增子序列还有二分的优化版本（时间复杂度 O(n log n)）。但优化的前提是二维的暴力写法你已经完全理解了，否则一维数组的"倒序遍历""覆盖顺序"解释起来特别费劲，自己写更容易整错。

5. 两个非常容易搞混的对比：完全背包和 LIS 的进阶坑

如果你上面五道题都吃透了，那再往下走，有两个进阶方向我认为特别值得单独说明，它们也是面试官喜欢往下追问的点。

5.1 01背包 vs 完全背包：循环顺序决定逻辑

零钱兑换实际上是"完全背包"的一种形式——每种物品无限取。把零钱兑换和01背包放在一起看，它们的转移方程很像，唯一的区别在于：01背包每件物品只能拿一次，完全背包每件物品可以拿无限次。这个区别表现在代码里，就是遍历的顺序：

# 01背包：外层循环物品，内层循环容量，容量必须倒序 def knapsack_01_1d(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity] # 完全背包：容量正序 def knapsack_complete_1d(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(weights[i], capacity + 1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity]

为什么01背包要倒序、完全背包要正序？这是一个教科书上写了但你未必真正理解的细节。

一维数组dp[j]在更新时，会覆盖掉之前的旧值。01背包里，我们要求dp[j - weights[i]]必须是**上一轮物品（前 i-1 件）**计算出来的值，也就是还没被当前物品更新过的历史值。如果正序循环，j从小到大，等处理到j时，较小的j - weights[i]可能已经在本轮被更新过了，这就相当于同一件物品被拿了多次，恰好变成完全背包的行为。倒序循环从大到小，j - weights[i]一定比j小，而它在本轮循环里还没被访问到，所以读到的还是上一轮的值，保证了每件物品只拿一次。

顺着这个逻辑你就明白完全背包为什么正序了——我们就是想让同一件物品可以被反复拿，正序更新时，dp[j - weights[i]]已经被本轮刷新过，包含了"当前这件物品已经拿过若干次"的情况，自然就实现了无限取用。

5.2 LIS 的O(n log n)优化：不只是为了复杂度

前面写的 LIS 版本是 O(n²)，数据量一上万就明显吃力。这里分享一个基于"贪心 + 二分"的优化方法，也是大厂面试喜欢追着问的。

核心思想：维护一个数组tails，tails[k]表示"长度为 k+1 的递增子序列中，结尾元素的最小值"。然后遍历数组，对每个元素，在tails里找到第一个大于等于它的位置，替换掉。如果找不到比它大的，说明它能接在现有最长子序列后面，直接 append。

import bisect def length_of_lis_binary(nums): tails = [] for x in nums: pos = bisect.bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x return len(tails)

拿[10, 9, 2, 5, 3, 7, 101, 18]走一遍：

• 10 → tails: [10]
• 9 → 替换10 → tails: [9]
• 2 → 替换9 → tails: [2]
• 5 → 比2大，append → tails: [2, 5]
• 3 → 替换5 → tails: [2, 3]
• 7 → append → tails: [2, 3, 7]
• 101 → append → tails: [2, 3, 7, 101]
• 18 → 替换101 → tails: [2, 3, 7, 18]

最终长度4。注意，tails里存的并不是真正的子序列，而是"每个长度的最小结尾"，但它能保证len(tails)等于最长递增子序列的长度。这个思路我第一次看的时候也转不过弯，后来想明白了一个关键点就通了："以更小的数字结尾"永远比"以更大的数字结尾"更有潜力——更小意味着后面能接更多更大的数，所以用一个最小值来代表某个长度是划算的。

5.3 五道题之外的举一反三

如果你已经能独立推导出上面几道题的转移方程，那么下面这些变体题你就可以尝试自己去做，思路全部来自上面：

• 打家劫舍（一维DP，和爬楼梯类似但变成了求最大值）
• 最大子数组和（状态定义是"以 i 结尾"，和 LIS 很像，转移方程更简单）
• 编辑距离（二维DP，和最长公共子序列共享框架）
• 分割等和子集（本质是01背包的"能凑出某个和"的判定问题）
• 不同的二叉搜索树（有点难，但状态定义和转移方程依然能顺着推）

6. 源码能跑通只是第一步：这些隐性问题你一定也会遇到

代码写出来能跑通，对动态规划来说只算完成了一半。真正考验人的是你跑一些特殊数据或者重新优化时冒出来的问题。这些坑我基本都踩过，列出来帮你省点时间。

6.1 初始化到底该是0还是infinity

这是个特别常见的问题。原则很简单：求最大值，初始化为0；求最小值，初始化为无穷大。但如果题目有额外的条件，比如"要求结果必须能由子问题拼出来"（像零钱兑换），初始化为float('inf')后就一定别忘了在最后判断不可达的情况。还有一个小细节是 dp 数组长度该开n还是n+1。我建议只要状态定义里包含"前 i 个""前 j 个"这种下标语义，一律开n+1，把下标0留出来做边界，代码写起来会顺手非常多，也能避免很多越界问题。

6.2 下标偏移是字符串类DP最大的坑

拿最长公共子序列来说，dp[i][j]对应的是text1[i-1]和text2[j-1]，不是text1[i]和text2[j]。因为dp[i][j]表示的是"前 i 个字符"和"前 j 个字符"，字符下标从0开始，所以第 i 个字符实际是text1[i-1]。这个偏移关系没搞清，写循环的时候一定迷迷糊糊，调试起来还特别费劲。我的经验是：先在代码注释里把状态定义完整写出来，再动手写循环。比如：

# dp[i][j]: text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度 # 所以当 text1[i-1] == text2[j-1] 时，说明新的一对字符相等

这样写着写着就不会晕了。

6.3 不要把 dp 的值和题目给的元素值搞混

这是新手经常出现的认知混乱。dp[i]存的是"答案的值"（方法数、长度、最大收益），不是原数组nums[i]的值。比如 LIS 里dp[i]表示以第 i 个元素结尾的最长子序列长度，它跟nums[i]没有直接数值关系，比较大小的对象是nums[j]和nums[i]，做加法的对象才是dp[j] + 1。我见过有人写出if dp[j] < dp[i]这种比较，一看就是把题意理解歪了。

6.4 空间优化的时候，注意维度压缩的方向

01背包压缩成一维数组的时候要倒序遍历容量，这是最常见的优化形式。但如果你优化的是一个二维的DP表，比如最长公共子序列，通常是用滚动数组只保留上一行和当前行。这里有个容易出错的地方：滚动数组的当前行在更新时，会覆盖上一行的旧值，所以dp[i-1][j-1]这种值要先保存下来再用。

def longest_common_subsequence_roll(text1, text2): m, n = len(text1), len(text2) prev = [0] * (n + 1) curr = [0] * (n + 1) for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: curr[j] = prev[j - 1] + 1 else: curr[j] = max(prev[j], curr[j - 1]) prev, curr = curr, prev return prev[n]

注意curr[j] = max(prev[j], curr[j - 1])里的curr[j-1]，它必须是本行已经算出来的那个值，而不是上一行的prev[j-1]，这是滚动数组写法里最隐蔽的坑之一。写完之后建议拿几个测试用例，手工对比二维版本的输出，确认一致再放心。

6.5 肉眼填表法：调试动态规划的王牌技巧

最后分享一个我用了很多年的笨但极其有效的方法——打印 dp 表。不论哪道题，跑完循环后把整个 dp 二维数组打印出来，一行一行对照着看，你的逻辑漏洞一定会自己跳出来。尤其是01背包这种，明明感觉转移方程没写错，输出值却差一点，填一遍表马上就知道是初始化错了还是循环边界错了。

# 以01背包为例，打印整个 dp 表 def knapsack_with_debug(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if weights[i - 1] <= j: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) else: dp[i][j] = dp[i - 1][j] print(f"第{i}件物品处理后: {dp[i]}") return dp[n][capacity]

我现在遇到复杂的新题，第一版永远是"二维dp + 打印表"，跑通了才开始考虑空间优化。想一步到位直接写一维优化版本，出了问题反而更浪费时间。

动态规划这个东西，说破天也就是"状态、转移、边界"六个字，但真正让它变得难以上手的，是"怎么从题目描述里看出这三样东西"的翻译过程。我自己的体会是，没有捷径，只有靠足够的题目量喂出来。不需要一天刷二十道，但每道题都按"暴力递归 → 记忆化搜索 → 动态规划"的思路过一遍，画一次递归树，填一次dp表，比囫囵吞枣刷一页题要管用得多。等你熟练到能把这一类题的题型归纳成几张大表，再拿到新题的时候，就会有种"哦，这个换了个皮而已"的轻松感了。