企业官网建设流程全解析

打开 LeetCode 刷题列表，动态规划专题往往是劝退新手的第一道高墙。“dp[i] = max(dp[i-1] + nums[i], nums[i])”“if s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + 1”……满屏的状态转移方程让人头皮发麻，于是很多人选择死记硬背，结果题目一变形，立刻歇菜。

这篇文章不打算让你背任何一个方程。我会带你从最朴素的递归开始，一步步通过“暴力递归 → 记忆化搜索 → 迭代动态规划”的路线，亲手推导出动态规划解法。再用背包、LIS（最长递增子序列）、LCS（最长公共子序列）三道经典题，把这条推导链路走通。读完你应该具备一种能力：遇到一道新 DP 题，至少知道怎么下手，而不是先去搜题解。

1. 动态规划到底是什么

1.1 用大白话理解动态规划

动态规划（Dynamic Programming，DP）听名字很高级，核心思想其实就一句话：把一个大问题拆成若干有重叠的小问题，先解决小问题，再组合出大问题的答案。

举个例子，你想计算自己从 1 楼爬到 10 楼有多少种走法，每次可以跨 1 级或 2 级台阶。你不需要真的去枚举每条路径，你只需要知道：

• 到第 9 楼的走法数，加上最后跨 1 级；
• 到第 8 楼的走法数，加上最后跨 2 级。

所以：

到第 10 楼的走法 = 到第 9 楼的走法 + 到第 8 楼的走法

这就是一个典型的递推关系，你不需要关系中间每一层具体怎么走的，只要知道数量。动态规划做的就是类似的事情：利用子问题的答案，递推得到父问题的答案。

1.2 什么题目适合用动态规划

判断一道题能不能用 DP，一般看两个特征：

1. 最优子结构：大问题的最优解可以由子问题的最优解组合而成。
2. 重叠子问题：在递归求解过程中，同一个子问题会被反复计算多次。

这两个特征同时出现时，动态规划通常能派上用场。比如求最短路径：从 A 到 D 的最短路，如果必经 B，那么 A 到 D 的最短路可以拆成 A 到 B 的最短路加上 B 到 D 的最短路。这里既有子问题，又会反复计算中间节点的最短路，符合 DP 的特征。

1.3 为什么不要背状态转移方程

状态转移方程是 DP 解题的“结果”，不是“原因”。它描述的是“子问题之间如何递推”，但这个关系本身是从题目逻辑里推导出来的。

如果你跳过分析过程，直接背“dp[i] = max(dp[i-1], dp[i-2] + nums[i])”，那么当题目变成“不能取相邻元素”、“环形数组”、“需要输出具体方案”时，方程稍微一变，你就认不出来了。

正确的学习路径是：

审题 → 定义递归函数（描述子问题） → 写暴力递归 → 加缓存（记忆化搜索） → 把递归改成递推 → 观察能否压缩空间

这条路径每一步都有章可循，不需要灵光一现，也不依赖背诵。

2. 环境准备与刷题工具

动态规划是算法题，对运行环境要求不高。你只需要满足下面条件就可以开始：

• 任意一种编程语言的基础语法能力（本文示例用 Python 和 Java，两版逻辑一致）。
• 一个能运行代码的环境：本地 IDE（IDEA、PyCharm、VS Code）或在线代码运行平台都可以。
• 如果使用 LeetCode，建议直接在网页编辑器里写，方便提交验证。

本文所有代码示例都按“核心函数 + 调用示例”的方式给出。Python 示例使用 3.8+ 版本，Java 示例使用 JDK 8+ 版本即可运行，不需要额外引入第三方依赖。

3. 核心思想：从递归到 DP 的三步推导法

为了让你彻底扔掉“背方程”的拐杖，我把动态规划的思考过程固定成三步，后面所有例题都按这个流程走。

3.1 第一步：定义递归函数

拿到题目后，先不要想“dp 数组怎么开”，而是问自己一个问题：我能不能用一个递归函数 f(n) 来描述我要求的答案？

• f(n) 的输入是什么？
• f(n) 的输出是什么？
• f(n) 和更小的 f(n-1)、f(n-2) 有什么关系？

这一步要求你具备“把问题规模缩小”的直觉。比如“爬楼梯”问题，f(n) 表示爬到第 n 阶有多少种方法；比如“最长递增子序列”问题，可以定义 f(i) 表示以第 i 个元素结尾的最长递增子序列长度。

定义好递归函数后，马上写递归出口（base case），然后尝试写出递归调用关系。这一步不追求性能，只要逻辑对就行。

3.2 第二步：加缓存，变成记忆化搜索

递归写出来之后，你会发现很多子问题被重复求解。比如 f(10) 会调用 f(9) 和 f(8)，f(9) 又会调用 f(8) 和 f(7)，这里 f(8) 被算了两次。

解决办法很简单：用一个数组或哈希表把已经算过的 f(k) 存起来，下次再需要 f(k) 时直接返回缓存结果。

这一步的代码改动很小，但能把指数级的时间复杂度降到多项式级别。此时你已经得到了一个“能用但可能栈溢出”的递归版本。

3.3 第三步：改成迭代递推，并考虑空间优化

递归是“自顶向下”，从大问题一路拆到小问题；迭代是“自底向上”，先算最小的子问题，再逐步组合出大问题。

迭代递推的好处是：

• 避免递归调用栈过深。
• 代码通常更简洁。
• 容易进一步做空间压缩。

改写方式也很固定：把递归函数的参数映射成数组下标，把递归出口映射成数组初始值，把递归调用关系映射成循环里的状态转移。

如果是二维 DP，则用二维数组；如果递推时只用到了前一行或前一个值，还可以用滚动数组优化空间。

3.4 一个立刻能上手的例子：斐波那契数列

我们拿最经典的斐波那契数列串一遍三步法。题目：求斐波那契数列的第 n 项，F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。

第一步，定义递归函数。

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

第二步，加缓存。

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

第三步，改成迭代递推。

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

观察一下，递推时 dp[i] 只依赖 dp[i-1] 和 dp[i-2]，所以可以把一维数组再压缩成两个变量：

def fib(n): if n <= 1: return n prev2, prev1 = 0, 1 for _ in range(2, n + 1): cur = prev1 + prev2 prev2 = prev1 prev1 = cur return prev1

以上就是动态规划完整推导链路的缩影。很多初学者直接看第三步的代码，会觉得“这不就是把数学公式翻译一下吗”，从而误以为 DP 就是找递推公式。实际上，真正的难点在第一、二步：你能不能自然地从题目描述中抽象出递归关系。

4. 实战案例：从递归推导三个经典动态规划模型

接下来我们完整走三个最常考的 DP 模型：0-1 背包、最长递增子序列（LIS）、最长公共子序列（LCS）。每一题我都严格按照“递归 → 记忆化 → 迭代递推”的顺序展开，你可以亲手敲一遍，感受 DP 是如何“长”出来的。

4.1 案例一：0-1 背包问题

4.1.1 题目描述

有 N 件物品和一个容量为 W 的背包。每件物品有重量 wt[i] 和价值 val[i]，每种物品只能选择放入或不放入一次，求能装入背包的最大总价值。

经典的 0-1 背包问题。为什么叫“0-1”？因为每件物品只有两种状态：取（1）或不取（0）。

4.1.2 递归定义

直接想 dp 数组可能有点抽象，我们先定义递归函数：

f(i, c) = 在前 i 件物品中做选择，背包剩余容量为 c 时，能获得的最大价值

对于第 i 件物品，我们有两种选择：

• 不选：问题变成 f(i-1, c)。
• 选：前提是 c >= wt[i]，问题变成 val[i] + f(i-1, c - wt[i])。

所以递归关系是：

f(i, c) = max( f(i-1, c), val[i] + f(i-1, c - wt[i]) )

递归出口有两个：

• 没有物品可选时，价值为 0，即 i < 0 时返回 0；
• 背包容量不足时，不能选当前物品。

用 Python 写暴力递归如下：

def knapsack_recursive(wt, val, i, c): # 没有物品可选或容量为负 if i < 0 or c <= 0: return 0 # 当前物品放不下，只能跳过 if wt[i] > c: return knapsack_recursive(wt, val, i-1, c) # 不选 vs 选，取较大值 no_take = knapsack_recursive(wt, val, i-1, c) take = val[i] + knapsack_recursive(wt, val, i-1, c - wt[i]) return max(no_take, take) wt = [2, 3, 4, 5] val = [3, 4, 5, 6] n = len(wt) capacity = 8 print(knapsack_recursive(wt, val, n-1, capacity))

运行结果：

10

解释：选择物品 0（重量 2，价值 3）、物品 1（重量 3，价值 4）、物品 3（重量 5，价值 6）总重量 10 超过容量 8。实际上最优方案是物品 0 + 物品 1 + 物品 2 = 重量 9 也超过。再调整：物品 0 + 物品 2 = 重量 6，价值 8；物品 1 + 物品 3 = 重量 8，价值 10。所以最大价值是 10。

这个递归版本在 N 和 W 稍大时会非常慢，因为递归树是二分支的，时间复杂度接近指数级。我们把递归过程画出来就能看到大量重复计算，比如 f(2, 5) 可能在不同分支里反复出现。

4.1.3 加缓存（记忆化搜索）

加一个 memo 二维数组，记录每个 (i, c) 的结果。因为 i 的范围是 0 到 N-1，c 的范围是 0 到 W，所以开一个(N) x (W+1)的数组就够了。用 -1 表示尚未计算。

def knapsack_memo(wt, val, W): n = len(wt) memo = [[-1] * (W + 1) for _ in range(n)] def dfs(i, c): if i < 0 or c <= 0: return 0 if memo[i][c] != -1: return memo[i][c] if wt[i] > c: memo[i][c] = dfs(i-1, c) else: no_take = dfs(i-1, c) take = val[i] + dfs(i-1, c - wt[i]) memo[i][c] = max(no_take, take) return memo[i][c] return dfs(n-1, W) wt = [2, 3, 4, 5] val = [3, 4, 5, 6] print(knapsack_memo(wt, val, 8))

运行结果同样是：

10

这个版本的时间复杂度已经降到 O(NW)，空间复杂度也是 O(NW)。递归仍然存在栈深度风险，但对常规测试数据已经可用了。

4.1.4 改写成迭代 DP

递归是“从后往前”思考，迭代 DP 可以“从前往后”填表。我们定义 dp[i][c] 表示“从前 i 件物品中选，容量为 c 时能获得的最大价值”。注意这里 i 从 1 开始计数，方便留出 i=0 表示“没有物品”。

状态转移：

• 不选第 i 件物品：dp[i][c] = dp[i-1][c]；
• 选第 i 件物品：dp[i][c] = dp[i-1][c-wt[i-1]] + val[i-1]（前提 c >= wt[i-1]）。

代码如下：

def knapsack_dp(wt, val, W): n = len(wt) dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): for c in range(1, W + 1): if wt[i-1] > c: dp[i][c] = dp[i-1][c] else: dp[i][c] = max(dp[i-1][c], dp[i-1][c-wt[i-1]] + val[i-1]) return dp[n][W] wt = [2, 3, 4, 5] val = [3, 4, 5, 6] print(knapsack_dp(wt, val, 8))

运行结果：

10

4.1.5 一维数组空间优化

观察状态转移方程，dp[i][c] 只依赖 dp[i-1][c] 和 dp[i-1][c-wt[i-1]]，也就是“上一行”的数据。因此我们不需要保留完整的二维表，只需要一行长度为 W+1 的数组，每轮从后往前更新即可。

为什么要从后往前？因为 dp[c] 更新时用到的是“上一轮较小容量 c-wt[i-1] 的值”。如果从前往后更新，dp[c-wt[i-1]] 可能已经被本轮覆盖，导致同一件物品被重复放入，那就变成完全背包了。

def knapsack_dp_1d(wt, val, W): n = len(wt) dp = [0] * (W + 1) for i in range(n): # 逆序遍历容量，防止物品被重复选择 for c in range(W, wt[i] - 1, -1): dp[c] = max(dp[c], dp[c - wt[i]] + val[i]) return dp[W] wt = [2, 3, 4, 5] val = [3, 4, 5, 6] print(knapsack_dp_1d(wt, val, 8))

输出结果依然是：

10

对照四个版本的代码，你能清楚地看到“递归定义 → 缓存 → 递推 → 空间优化”这条演变路径。面试时如果要求输出最优方案的具体物品，就需要回退到二维 DP，额外记录选择路径。

4.2 案例二：最长递增子序列（LIS）

4.2.1 题目描述

给定一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列不要求连续，但要保持原数组中的相对顺序。

例如：

nums = [10, 9, 2, 5, 3, 7, 101, 18] 最长递增子序列是 [2, 3, 7, 101]，长度为 4

4.2.2 递归定义

很多同学第一次接触 LIS 时，会想当然地定义 f(i) 为“前 i 个元素的最长递增子序列长度”。但这个定义有问题：你无法从前 i-1 个元素的结果直接推导出第 i 个元素加入后的结果，因为你不知道前 i-1 个元素的最长递增子序列末尾元素是谁，也就无法判断第 i 个元素能不能接在后面。

正确的做法是定义：

f(i) = 以 nums[i] 结尾的最长递增子序列长度

为什么这样定义？因为“以某个元素结尾”把子序列的结束位置固定住了，这样后续状态转移时，我们只要比较“当前元素能否接在某个前面的元素后面”即可。

递归关系：

• 初始化 f(i) = 1，因为单个元素自身可以构成长度为 1 的递增子序列。
• 对于每个 j < i，如果 nums[j] < nums[i]，那么 f(i) 可以考虑从 f(j) + 1 转移过来。

对应的递归思路可以写成：

f(i) = 1 + max( f(j) )，其中 j < i 且 nums[j] < nums[i]

如果没有任何满足条件的 j，那么 f(i) = 1。

4.2.3 暴力递归到记忆化搜索

用 Python 写一个自顶向下的版本。递归函数 dfs(i) 表示“以 nums[i] 结尾的最长递增子序列长度”。

def length_of_lis_memo(nums): n = len(nums) memo = [0] * n def dfs(i): if memo[i] != 0: return memo[i] best = 1 for j in range(i): if nums[j] < nums[i]: best = max(best, dfs(j) + 1) memo[i] = best return best ans = 0 for i in range(n): ans = max(ans, dfs(i)) return ans nums = [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_memo(nums))

运行结果：

4

这段代码里 dfs(i) 会递归地去找前面所有比 nums[i] 小的元素，把它们的 LIS 长度算出来再加 1。

4.2.4 迭代 DP 版本

把自顶向下的递归改成自底向上的双重循环：

def length_of_lis_dp(nums): n = len(nums) if n == 0: return 0 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) nums = [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_dp(nums))

运行结果：

4

这个版本的时间复杂度是 O(n²)，空间复杂度是 O(n)。

4.2.5 进阶：贪心 + 二分优化到 O(n log n)

LIS 还有一个非常经典的优化思路，用tails数组维护“长度为 k 的递增子序列的最小末尾元素”。遍历每个元素时，在 tails 中二分查找第一个不小于当前元素的位置并替换；如果当前元素比 tails 中所有元素都大，就追加到末尾。

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) nums = [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_binary(nums))

结果仍然是：

4

注意：tails 数组本身并不一定是真实的 LIS 序列，它只是用来辅助计算长度的。这个方法适合只求长度、不要求输出具体序列的场景。

4.3 案例三：最长公共子序列（LCS）

4.3.1 题目描述

给定两个字符串 text1 和 text2，返回两个字符串的最长公共子序列的长度。子序列可以不连续，但相对顺序必须一致。

例如：

text1 = "abcde" text2 = "ace" 最长公共子序列是 "ace"，长度为 3

如果两个字符串没有公共子序列，返回 0。

4.3.2 递归定义

LCS 问题是一个典型的二维 DP。我们定义递归函数：

f(i, j) = text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度

其中 i 和 j 可以取 0，表示空字符串。递归关系分两种情况：

1. 如果 text1[i-1] == text2[j-1]，说明当前两个字符可以匹配，那么：

f(i, j) = f(i-1, j-1) + 1

2. 如果不相等，则当前字符不可能同时出现在公共子序列中，只能选择丢弃 text1 的最后一个字符，或者丢弃 text2 的最后一个字符：

f(i, j) = max( f(i-1, j), f(i, j-1) )

递归出口：

f(0, j) = 0 f(i, 0) = 0

因为空字符串和任何字符串都没有公共字符。

4.3.3 暴力递归到记忆化搜索

先写一个自顶向下的递归版本：

def lcs_memo(text1, text2): m, n = len(text1), len(text2) memo = [[-1] * (n + 1) for _ in range(m + 1)] def dfs(i, j): if i == 0 or j == 0: return 0 if memo[i][j] != -1: return memo[i][j] if text1[i-1] == text2[j-1]: memo[i][j] = dfs(i-1, j-1) + 1 else: memo[i][j] = max(dfs(i-1, j), dfs(i, j-1)) return memo[i][j] return dfs(m, n) print(lcs_memo("abcde", "ace"))

运行结果：

3

这里 memo[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。注意递归函数与数组下标从 1 开始，和字符串下标差一位。

4.3.4 迭代 DP 版本

把递归改成双层循环，自底向上填表。dp[i][j] 的含义与 memo[i][j] 一致。

def lcs_dp(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(lcs_dp("abcde", "ace"))

运行结果：

3

4.3.5 空间优化

LCS 的二维表也可以压缩成一行，因为 dp[i][j] 更新时依赖三个位置：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。如果只保留上一行的一维数组，我们需要用一个临时变量记录 dp[i-1][j-1]（对应左上角的值）。

def lcs_dp_1d(text1, text2): m, n = len(text1), len(text2) dp = [0] * (n + 1) for i in range(1, m + 1): prev = 0 # 相当于 dp[i-1][j-1] for j in range(1, n + 1): temp = dp[j] # 保存当前 dp[j]，它是下一轮循环的“上一行左上角” if text1[i-1] == text2[j-1]: dp[j] = prev + 1 else: dp[j] = max(dp[j], dp[j-1]) prev = temp return dp[n] print(lcs_dp_1d("abcde", "ace"))

结果还是：

3

这个压缩过程理解起来比一维背包略复杂，核心是搞清楚prev变量保存的是哪个历史状态。建议你先跑通二维版本，再对照二维表中“当前行覆盖上一行”的过程来理解一维版本，不要一上来直接硬啃。

5. 动态规划学习中的常见问题与排查思路

很多新手自己做 DP 题报错时，第一反应是去改代码，但其实问题出在“对子问题的定义”上。我整理了刷题时最容易遇到的几类问题，帮你对症下药。

5.1 如何定位递归中的重复计算

如果你不确定自己的递归是否存在大量重复计算，可以在递归函数里加一个计数器，或者打印递归调用参数。比如：

def dfs(i, c): print(f"call dfs({i}, {c})") ...

如果看到相同的 (i, c) 反复出现，就说明存在重叠子问题，有必要使用记忆化搜索。

5.2 状态定义不清晰导致的玄学报错

这是 DP 新手最隐蔽的坑。以 LIS 为例，如果你把 f(i) 定义成“前 i 个元素的最长递增子序列长度”，那么当 nums[i] 很小但前面的最长递增子序列末尾很大时，你是无法判断能不能把 nums[i] 接上去的。这会导致递推关系无法建立，或者结果错误。

遇到这种情况，解决问题的关键不是改代码，而是回头重新定义状态。一个常用的技巧是：增加约束条件，让子问题之间能够“衔接”。LIS 中“以第 i 个元素结尾”就是一种常见的约束。

5.3 对着题解能看懂，自己写就卡住

这是正常的学习曲线。建议你不要只看题解代码，而是找一道中等难度 DP 题，按照“递归定义 → 暴力递归 → 记忆化 → 迭代 DP”的顺序，自己从头到尾完整推一遍。这个过程会强迫你把“状态怎么转移”讲清楚，而不是被动接受现成的 dp 方程。

6. 动态规划的最佳实践与刷题建议

6.1 先画递归树，再写代码

拿到一道 DP 题，不要急着敲键盘。在草稿纸上画出小规模输入的递归树，标注哪些节点被重复计算。这个动作能帮你同时验证“子问题是否重叠”和“递归关系是否正确”。

比如爬楼梯问题，n=5 的递归树中 f(3) 会出现两次，f(2) 会出现三次，画出来之后你自然理解为什么要记忆化。

6.2 状态定义口诀：最后一步看什么，状态就存什么

如果你不知道 dp 数组的每个维度代表什么，可以问自己一个终极问题：当我只差最后一步就能得到答案时，我需要知道哪些信息？

• 背包问题：需要知道还剩多少容量，以及已经处理到第几件物品，所以状态是 f(i, c)。
• LIS：需要知道当前递增子序列以哪个元素结尾，所以状态是 f(i)。
• 编辑距离：需要知道两个字符串分别处理到哪个位置，所以状态是 f(i, j)。

这个“最后一步分析法”有时候比生搬套路更有效，建议你在做题时反复练习。

6.3 用一维还是二维，取决于状态依赖关系

很多同学会陷入“必须写出空间最优解”的执念。实战中建议你：

1. 先用最直观的二维 DP 写出正确版本；
2. 提交通过后，再考虑能否用滚动数组或一维数组优化；
3. 优化前，用注释列出一维数组更新时可能覆盖的旧值，再动手改代码。

空间优化是锦上添花，不是雪中送炭。面试时如果时间紧张，先写出正确解比写出最优解更重要。

6.4 刷题顺序建议

如果你的动态规划还处于入门阶段，不推荐直接挑战困难题。可以参考下面这个难度递增路径：

1. 爬楼梯、斐波那契数列：体会“递推 + 空间压缩”；
2. 不同路径、最小路径和：体验二维 DP 表格怎么填；
3. 最长递增子序列、最长公共子序列：练习子序列类模型；
4. 0-1 背包、完全背包：掌握最经典的背包模型；
5. 打家劫舍系列、买卖股票系列：练习状态机式 DP；
6. 区间 DP、树形 DP：进阶方向，按需学习。

每一步都要保证自己能用“递归 → 记忆化 → 递推”的流程独立推导出来，再进入下一类题。

6.5 关于代码的工程习惯

刷题代码和生产代码要求不同，但以下习惯值得保持：

• 函数命名清晰，让别人一眼知道这个函数在算什么；
• 状态数组的语义用注释说明，例如dp[c]表示“容量为 c 时的最大价值”；
• 把 base case 单独写清楚，不要藏在循环条件里；
• 写完代码后用一组边界数据自测：空输入、最小输入、最大输入、相等元素输入。

如果你在本地 IDE 中练习，还可以自己写一个简单的测试函数，批量断言结果，便于后续回归：

def test_lis(): assert length_of_lis_dp([10, 9, 2, 5, 3, 7, 101, 18]) == 4 assert length_of_lis_dp([0]) == 1 assert length_of_lis_dp([]) == 0 print("all test cases passed") test_lis()

7. 总结

动态规划并不可怕，可怕的是用背题的方式去学它。这篇文章的核心观点是：状态转移方程不是背出来的，而是从递归定义里一步步推出来的。

我们完整走通了三条推导路径：

• 0-1 背包：从 f(i, c) 的递归定义出发，经过记忆化搜索，改写成二维递推，最终压缩成一维逆序更新；
• 最长递增子序列：从 f(i) 表示“以 nums[i] 结尾”的递归定义出发，推导出 O(n²) 的 DP，再介绍了 O(n log n) 的二分优化；
• 最长公共子序列：从二维递归 f(i, j) 出发，对照字符相等和不相等两种情况，推导出二维填表逻辑，再分析了空间压缩的细节。

如果你能把这三种模型的推导过程自己复现一遍，再去做 LeetCode 上的同类变体题（比如跳跃游戏、编辑距离、零钱兑换），会发现这些题远没有想象中难。关键在于先想清楚一件事：我正在求解的子问题是什么？它和我已经解决过的更小子问题之间是什么关系？想清楚这个，代码只是顺手的事。

拿一道题练手吧：LeetCode 300 最长递增子序列，或者 LeetCode 1143 最长公共子序列，先别看题解，按文中的三步法自己推一遍。遇到卡壳的地方，回来对照文章的推导过程看看自己是在状态定义、递归关系、还是边界处理上出了问题。多推几道，你就能慢慢建立属于自己的动态规划直觉了。