企业官网建设流程全解析

我最早学动态规划的时候，最大的感受是：所有教程都在抛“状态转移方程”，但没人告诉我这个方程是怎么被想出来的。后来把找零钱、最大连续子序列和、最长上升子序列、最长公共子序列、最长公共子串、0-1背包这六个经典问题放在一起反复对比，才慢慢摸到门路：动态规划不是靠灵感，而是一套有固定拆解方法的思维方式。这篇文章我想把这些问题的状态设计思路、转移方程的推导过程、初始化细节、空间优化技巧和踩坑记录一次性讲清楚，适合刚学完递归、准备认真啃动态规划的读者，也适合已经会写一些DP题但总觉得不够系统的朋友。我尽量只讲方法论和实操细节，不堆术语，不做“一看就会、一写就废”的那种空谈。

1. 动态规划的基本框架：状态、转移、初始化

1.1 状态：给“局面”拍照

动态规划的第一步，不是急着找公式，而是先想清楚一个问题：我手上现在掌握什么样的情况，才能唯一确定接下来该怎么做？

这个“情况”通常会成为状态。比如找零钱问题，当前金额就是局面，因为无论之前用了多少枚硬币，只要剩余金额相同，未来能做出的最优选择一定相同。比如最大连续子序列和，状态是“以某个位置结尾”，因为一旦确定结尾位置，就不需要管这个子序列从哪里开始，只需要知道它之前累加的结果。再比如0-1背包，状态是“已经处理到第几件物品、当前还剩多少容量”，这两条信息缺一不可。

我习惯把状态理解成给一个局面拍一张快照：快照里包含的参数越少越好，但必须保证无法再区分不同历史时，未来的决策是一样的。这个“少而全”的平衡点，是DP状态设计的核心。初学者最容易犯的错是状态定义过粗，比如找零钱只写“金额”，却不考虑“剩余金额”和“已用硬币数”之间的因果关系；或者状态定义过细，把每一步用了哪枚硬币都记录进去，结果状态变成全排列，无法合并子问题。

1.2 转移：描述局面怎么变

有了状态，第二步要回答“局面是怎么一步步走到现在的”。这个“怎么走到”就是转移方程。

写转移方程时，我常用一个很朴素的问法：站在当前状态，我上一步做了什么？找零钱问题的答案是“我最后放进去了一枚某面额的硬币”，所以当前金额的最少硬币数，是由“更小的金额的最少硬币数再加一枚”产生的。最大连续子序列和的答案是“当前元素要么自己重新开头，要么拼在前一个最优连续段的末尾”，所以才有那个经典的二选一。0-1背包的答案是“我面对当前物品时，要么不装它，要么腾出重量把它装进去”，于是转移两端自然出现。

转移的方向也很重要。自底向上填表，要保证计算当前状态时，依赖的状态已经算完；自顶向下递归，则要保证没有环状依赖，否则会无限递归。判断标准就一条：转移涉及的参数，是否始终朝着“规模更小”的方向推进。如果是，递推表和记忆化递归都能做；如果不是，说明状态设计有问题，需要返工。

1.3 初始化：边界值的另一种说法

初始化不是单独背下来的，而是状态定义在“最小局面”下的自然结果。找零钱的dp[0]等于0，是因为“金额为0时不需要任何硬币”；最长上升子序列的dp[i]初始化为1，是因为“每个元素本身就能成为一个长度为1的上升子序列”；背包的dp[0][j]等于0，是因为“一件物品都没放，价值自然是0”。

一个很常见的错误，是把极大值、极小值、0、1这几种初始化混用。我自己的经验是，先把递推公式在纸上写出来，再把几个边界情况代入验算，比如金额为0、序列为空、容量为0。代入后如果结果与常识不符，多半是初始化错了。初始化错的典型表现是：小规模样例能过，规模稍大就完全不对，原因在于错误会顺着递推关系层层放大。

2. 找零钱：第一次用DP解决“选择”问题

2.1 问题描述与暴力递归

找零钱问题是这样的：给定一组硬币面额，比如1、5、11，再给一个总金额，比如15，问最少用几枚硬币能凑出这个金额，硬币可以重复使用。

我第一次看到这道题时，第一反应是贪心：每次先用最大面额去凑，11加4个1，得到5枚。可最优解明明是3枚5元硬币。贪心之所以会翻车，是因为局部最大的选择会破坏整体最优。这时就需要一种能“回头比较”所有可能方案的方法，动态规划正好能提供这种能力。

最直观的写法是暴力递归：定义f(amount)表示凑出amount需要的最少硬币数。如果amount等于0，返回0；否则枚举每一种硬币c，如果c不超过amount，就尝试f(amount - c) + 1，最后取最小值。这个递归是正确的，但非常慢，因为f(amount)会被反复计算很多次。举例来说，f(15)会去算f(14)、f(10)、f(4)，而f(14)又会去算f(13)、f(9)、f(3)，子问题大量重叠，指数级膨胀。

2.2 从递归改造成填表

暴力递归慢，是因为同一个子问题被重复求解。解法也很朴素：把每个金额对应的结果存起来，算过就不再算第二遍。这就是记忆化递归；再进一步，直接把数组从下标0开始递推填满，就是标准动态规划。

用数组dp[i]表示凑出金额i需要的最少硬币数，初始化dp[0]=0，其余为无穷大。然后遍历i从1到amount，对于每个硬币c，如果c不超过i，就更新dp[i]=min(dp[i], dp[i-c]+1)。最后dp[amount]就是答案；如果它仍然是无穷大，说明凑不出来，返回-1。

def coin_change(coins, amount): 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 -1 if dp[amount] == float("inf") else dp[amount]

这段代码的复杂度是O(amount乘以硬币种数)，空间是O(amount)。实际使用时要注意，amount可能是0，此时dp数组长度是1，直接返回0即可；硬币面额也可能大于amount，循环里的if自然会跳过，不需要额外处理。

2.3 为什么硬币无限也可以套用背包思想

找零钱本质上是“物品数量无限”的背包问题，也就是完全背包问题的变形。硬币就是物品，金额就是容量，每枚硬币的价值是1，目标是总重量等于容量时价值最小。因为硬币可以任意重复使用，所以递推时不需要限制“每个硬币最多一次”，这也是它和0-1背包最大的区别。后面聊到0-1背包时，我会仔细对比两者循环顺序的差异。

这道题还有一个容易忽略的点：硬币面额的顺序与答案无关。无论你先枚举金额还是先枚举硬币，最小数量都不会变，因为这里只关心“用了多少枚”，不关心“先放哪一枚”。所以找零钱的循环顺序相对宽松，给初学者的压力也小一点。等需要统计“具体怎么凑”时，顺序问题才真正变得敏感。

2.4 补充：统计凑法数量时要注意排列与组合

如果把问题改成“有多少种凑法”，状态定义基本不变，但转移方程要从“取最小值”变成“方案数求和”：dp[i] = sum(dp[i - c])，初始化dp[0]=1，表示空集是一种凑法。

这时候循环顺序就非常关键了。如果外层遍历金额、内层遍历硬币，得到的是排列数：比如用1、2、3凑3元，会同时统计“1+2”和“2+1”，因为同一金额在不同阶段会反复使用不同硬币。如果外层遍历硬币、内层遍历金额，得到的是组合数，因为每枚硬币被“固定”下来后就不会再回头考虑它的顺序。我在实际练习中踩过这个坑：题目明明要求组合数，我却用排列数写法交上去，样例只有一个所以没被发现，换一组数据立刻多算了很多。所以拿到题，先确认顺序重不重要，再决定两层循环的摆放方式。

3. 最大连续子序列和：一维DP的最佳入门

3.1 问题定义与暴力做法

题目本身一句话就能说清：给定一个整数数组，找出和最大的连续子数组，返回这个最大和。经典例子是[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最优子数组是[4, -1, 2, 1]，和是6。

暴力做法很好想：枚举所有可能的起点和终点，两层循环算出所有子数组和，取最大值，复杂度O(n^2)。数据量一大就会超时，而且这个问题的结构非常适合DP，不需要用更复杂的数据结构。说它是“一维DP的最佳入门”，是因为它的状态只有一维，转移方程只有一行，甚至连完整DP表都不用开，用一个变量就能滚动出答案。

3.2 状态转移方程的推导

关键一步是重新定义状态：不要想着“整个数组的最优子段”，而是想“以第i个元素结尾的最大连续子数组和是多少”。为什么这么定义？因为只有确定了结尾位置，才能描述“上一个元素到底有没有被包含进来”。

设dp[i]表示以nums[i]结尾的最大子数组和。那么当我站在元素i面前时，只有两种选择：要么把nums[i]接到前一个最优连续段的末尾，也就是dp[i-1] + nums[i]；要么重新开始一段，也就是只有nums[i]自己。取两者较大值，就是最优。所以转移方程为 dp[i] = max(nums[i], dp[i-1] + nums[i])。

这个方程背后的直觉，有点像“找工作要不要接受前一家公司的经验加成”：如果前面积累的收益是正数，带上它更赚；如果是负数，不如清零重来。正是这个“负数宁可不带”的规则，保证了段之间的连续性不会被无关元素破坏。

3.3 代码、复杂度与边界处理

理想情况下，我们甚至不需要开完整数组，因为dp[i]只依赖dp[i-1]。用一个cur变量保存“以当前位置结尾的最大和”，再用best变量保存历史最大值即可，空间降到O(1)。

def max_subarray(nums): if not nums: return 0 cur = nums[0] best = nums[0] for x in nums[1:]: cur = max(x, cur + x) if cur > best: best = cur return best

边界处理有两个很容易出错的地方。第一，空数组没有定义最大和，通常返回0或抛异常，具体看题目要求。第二，数组全为负数时，cur和best会一路取到最大值，比如[-5, -1, -3]的答案是-1，而不是0。很多新手会把best初始化为0，结果全负数组直接得0，这就不对了。正确做法是让best等于第一个元素，从第二个元素开始扫描。

4. 最长上升子序列：从 O(n²) 到 O(n log n)

4.1 题目背景与状态定义

最长上升子序列（Longest Increasing Subsequence，简称LIS）要求在一个无序序列中找出最长的严格递增子序列，子序列不要求连续，但必须保持原数组的相对顺序。比如[10, 9, 2, 5, 3, 7, 101, 18]，答案可以是[2, 3, 7, 101]，长度是4。

状态定义和最大连续子序列和很像：设dp[i]表示以nums[i]结尾的最长上升子序列长度。同样强调“以i结尾”，是为了让每个状态都能清晰知道“上一个元素是谁”。唯一不同是，最大连续子序列和只能把当前元素接到前一个相邻元素后面，而上升子序列可以接到前面任意一个比当前元素小的元素后面。

4.2 经典DP的完整实现

转移方程可以从定义直接读出：dp[i]等于所有满足j小于i且nums[j]小于nums[i]的dp[j]中的最大值，再加1。初始化时每个dp[i]都等于1，因为单元素子序列必然是上升子序列。

def length_of_lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

这个版本的时间复杂度是O(n^2)，空间是O(n)。写的时候要注意，内层循环必须遍历所有j，而不是只看i前面紧挨着的那个元素，否则会漏掉不连续递增的情况。比如[3, 1, 2]，只看前一个是2的dp值，会漏掉从1接上2的可能性；只有遍历j=1时，nums[j]=1小于2，dp[1]=1，才能算出dp[2]=2。

4.3 贪心 + 二分的优化思路

O(n^2)在n达到十万级别时撑不住，需要优化到O(n log n)。优化思路很有意思：不直接求“以谁结尾的最长长度”，而是维护一个数组tails，tails[len]表示“长度为len的上升子序列中，末尾元素的最小值”。

为什么这个数组有用？因为如果有两条长度相同的上升子序列，末尾更小的那条更有潜力继续变长，就像竞争岗位时手里资源更省的人更容易活下来。遍历原始数组时，对每个元素x，在tails里找到第一个不小于x的位置，把它替换成x；如果x比tails里所有元素都大，就追加到末尾。最终tails的长度就是答案。

import bisect def length_of_lis(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)

这里有个细节要多说两句。题目要求严格递增，所以重复元素不能接在相同元素后面，应该替换掉第一个不小于x的位置，也就是bisect_left；如果改成非严格递增，就应该用bisect_right，把相等的元素也当作“可以追加”，这样重复值才能算进长度。这个差异很隐蔽，我当年在某个在线评测平台上就因为这个二分函数选错，连挂三次。

4.4 重建具体上升序列

如果题目只问长度，上面的优化已经足够了。但如果要输出具体子序列，二分方案维护的tails数组并不能直接还原路径，因为tails在替换过程中并没有保留“谁把谁顶替掉”的关系。这时有两个选择：一是用O(n^2)的DP，额外开一个pre数组记录每个状态是从哪个j转移过来的，最后从最长长度的位置一路往前回溯；二是仍然用二分优化，但额外维护一个idx数组记录每个元素在tails中的位置，再配合原数组反推。

考虑到大多数场景下n不会特别大，我建议先掌握O(n^2)+pre数组的写法，因为思路清晰、不容易写错。只有在明文要求O(n log n)或数据量极大时，才去折腾二分重建法。训练时用“长度”版本练优化，用“输出序列”版本练回溯，分开练反而更高效。

5. 最长公共子序列与最长公共子串：两个序列DP的左手和右手

5.1 最长公共子序列的状态设计

最长公共子序列（Longest Common Subsequence，简称LCS）问题，给定两个字符串，要求找出同时是两个字符串子序列的最长长度。子序列不要求连续，比如“ABCBDAB”和“BDCABA”的最长公共子序列可以是“BCBA”，长度是4。

这个问题之所以经典，是因为状态变成二维：设dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。字符串下标偏移一位，是为了给i=0或j=0留出“空串”边界。

转移规则是逐字符比较。如果A的第i个字符等于B的第j个字符，那么这个字符一定能拼在之前已经匹配好的子序列后面，所以dp[i][j]=dp[i-1][j-1]+1。如果不相等，说明当前这两个字符不能同时进入子序列，答案只能从前一状态继承，取dp[i-1][j]和dp[i][j-1]的较大值。用一个不是很严谨但非常形象的类比：两个字符相等就“结婚”，不相等就只能看两人各自前一段谁更优秀。

def lcs(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[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]

5.2 回溯出完整子序列

如果只要求长度，上面代码已经结束。但很多题目会追问“最长公共子序列是什么”，这就需要回溯。方法是从dp表的右下角出发，倒着走回左上角。当前字符相等时，说明这个字符被计入了子序列，记录它并向左上移动；不相等时，比较dp[i-1][j]和dp[i][j-1]，谁大就往谁那侧移动，两者相等时可以任选一个方向。最后把记录下来的字符反转，就是答案。

# 接在上面的 dp 计算之后 res = [] i, j = m, n while i > 0 and j > 0: if a[i - 1] == b[j - 1]: res.append(a[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] >= dp[i][j - 1]: i -= 1 else: j -= 1 return ''.join(reversed(res))

回溯时要注意，如果dp[i-1][j]和dp[i][j-1]相等，选择哪边都可能得到正确长度但不同内容。所以当题目只要求“任意一个最长公共子序列”时，回溯写起来可以随意；如果要求字典序最小，则需要额外规定优先级。这个细节很容易被忽略。

5.3 最长公共子串：从“不连续”到“必须连续”

最长公共子串（Longest Common Substring）和最长公共子序列只差两个字，思路却要重新调一下。因为是子串，所以匹配的字符必须连续，一旦不连续，之前积累的长度立即作废。

dp[i][j]定义保持不变，但转移逻辑变成：如果A的第i个字符等于B的第j个字符，则dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]直接写0，表示以这两个字符结尾的公共子串长度为0。整体答案不再像LCS一样固定在dp[m][n]，而是所有dp值里的最大值，同时要记录最大值的下标，方便截取具体子串。

def longest_common_substring(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] best = 0 end_index = 0 for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > best: best = dp[i][j] end_index = i else: dp[i][j] = 0 return a[end_index - best: end_index] if best else ""

这段代码里，end_index记录的是A中当前最优子串结束位置的下一个字符下标，所以最后切片时用end_index - best作为起点。实际操作中，边界、索引、切片的下标非常容易错，建议在本地运行几次带样例的测试，把所有下标算清楚再提交。

5.4 两个问题的一页纸对比

到这一步，把两个问题放在一起看，差异非常清晰：

这张表值得抄在笔记本上。我见过不少同学把两个问题的转移方程混着写，最典型的表现是：子串问题用了max，导致一旦中间断开，前面的长度还能残留，结果答案“看起来很长”，实则片段不连续。记住一句话：子串是“断了就清零”，子序列是“断了还能继承”。

6. 0-1背包：最典型的“装与不装”

6.1 问题定义与二维状态表

0-1背包的描述是：有n件物品，每件物品有重量w[i]和价值v[i]，背包容量是W，每件物品只能选择装一次，问能装下的最大总价值。

它和找零钱最大的不同是“每件物品只能用一次”。这个限制看起来很小，但会让循环方向发生根本变化，如果不理解背后的原因，代码就会在“正序”和“逆序”之间反复翻车。

状态定义比较自然：dp[i][j]表示从前i件物品中挑选，容量不超过j时能获得的最大价值。第一维“前i件”用来控制可选物品范围，第二维“容量j”用来表达当前背包余量。初始化时，无论容量是多少，一件物品都不选，价值都是0，所以dp[0][j]=0。

6.2 转移方程与初始化细节

对于第i件物品，我只有两种选择：不装它，继承上一件物品在同样容量下的最优值dp[i-1][j]；装它，需要腾出w[i]的重量，获得v[i]的价值，即dp[i-1][j-w[i]]+v[i]，前提是j不小于w[i]。取两者最大值就是dp[i][j]。

二维写法先写出来，更容易理解：

def knapsack_2d(weights, values, W): n = len(weights) dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, W + 1): if j >= weights[i - 1]: 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] return dp[n][W]

这个版本的逻辑很直白，建议作为学习的第一版。初始化时，dp表里所有元素默认是0，等于天然处理了“容量为0”和“物品为空”的边界。需要注意的是，如果某些物品的重量为0，转移时需要照顾到重量为零的物品可以无限叠价值，这会变成一个特殊的完全背包问题，大多数题目会约定重量大于0，但也值得看一眼题目条件。

6.3 滚动数组优化：为什么必须逆序遍历

二维DP的时间是O(nW)，空间也是O(nW)。当W达到很大时，二维数组吃不消，需要把空间压成一维数组dp[j]，含义是“容量为j时当前能获得的最大价值”。

一维优化的关键，完全在于内层循环必须从大到小遍历容量。原因很简单：dp[j-w[i]]必须是上一件物品的状态，而不是当前物品更新过后的状态。如果从小到大遍历，当计算第i件物品的dp[j]时，dp[j-w[i]]可能已经被第i件物品更新过，相当于一件物品被反复使用，这就违背了“每件最多一次”的约束，反而变成了无限使用。逆序遍历可以保证dp[j-w[i]]仍然来自上一轮，因为容量小的位置在本次循环中还没有被当前物品覆盖。

def knapsack_1d(weights, values, W): dp = [0] * (W + 1) for i in range(len(weights)): for j in range(W, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[W]

如果题目改成完全背包，即每件物品可以不限次数使用，内层循环就从正序遍历，这样才能让当前物品反复参与更新。这也能反过来验证我前面说的：找零钱因为硬币无限，内层循环顺序不敏感，但背包因为物品有限，顺序成了天堑。建议大家拿一个具体的三件物品例子手动演算一遍正序和逆序的区别，比背十遍结论都管用。

6.4 如何还原选中的物品

一维数组只保存了最优值，丢掉了“从哪来”的信息。如果要输出选中的物品，最好保留完整的二维DP表，然后从右下角开始回溯：

# 假设已经用二维 dp 填好表 selected = [] j = W for i in range(n, 0, -1): if j >= weights[i - 1] and dp[i][j] == dp[i - 1][j - weights[i - 1]] + values[i - 1]: selected.append(i - 1) j -= weights[i - 1]

回溯逻辑是：如果dp[i][j]恰好等于“装下第i件物品”的状态，就说明最优方案里包含它；否则这个值一定等于不装它的状态dp[i-1][j]，就继续往前看。实际使用时要注意，如果物品价值恰好都是0或出现并列最优，回溯出的一组选择可能是其中一种，不一定唯一，但一定是合法的。这类“只求一组可行解”的题目，通常会在题目里注明“任意一组均可”。

6.5 找零钱、完全背包、0-1背包的三方对比

这三个问题经常被放在一起考，因为它们本质是同一族问题。下面这个对比，是我刷完几十道背包变体之后总结出来的：

最后一行的“均可”也有适用前提，就是只求最小数量，不关心顺序。一旦改为“统计凑法方案数”，循环顺序就必须按照组合数的规则来摆。理解了这一层，再看很多背包型数据结构题，能一眼看出它到底属于哪种变体。

7. 实战排查：动态规划里最容易踩的六个坑

7.1 初始化写错，整个DP表跟着歪

我的经验是，初始化错误通常不是写错一个数字，而是把状态定义和边界条件错配。比如LCS的dp表把第一行第一列初始化为1，就会把所有结果整体加偏移；找零钱把dp[0]初始化为1，会让方案数比正确值多出很多。排查方法很简单：用一个极小的样例手动填一遍表，看第一行、第一列、第一次循环的结果是否合理。如果第一遍填表就“看起来不对”，不用怀疑，先回去读状态定义。

7.2 滚动数组的遍历顺序搞反

背包问题中正序和逆序的后果是截然不同的：逆序是0-1背包，正序是无限使用物品。我自己在写代码时，会把“容量逆序”这四个字直接写在注释里。如果提交后发现答案比预期大，优先怀疑这里，因为正序会让同一件物品被反复累加价值，结果必然偏大，且偏大的程度会随容量上限迅速膨胀。

7.3 最长公共子串的答案存错位置

子串问题的答案不是固定在某一个角落，而是整个dp表的全局最大值。我有几次在写LCS之后顺手改子串题，只改了转移方程，忘了记录best和终止下标，结果返回的是dp表右下角的值。那个值往往比真实答案小，因为最后两个字符一旦不相等，右下角就会被强制写成0。排查这类问题，直接在计算过程中打印每次更新best时的行列号，能快速定位。

7.4 二分查找的边界条件

LIS二分优化里的bisect_left和bisect_right选择，直接决定了严格递增和非严格递增的结果。选错一次，正确性就错一半。我个人的检查方法是：把数组改成[1, 1, 1]，如果是严格递增，正确答案是1，用bisect_right就会错误地得到3；非严格递增则相反。这种特例输入，应该在提交前主动构造出来测一遍。

7.5 组合数写成排列数

找零钱方案数里，外层遍历硬币是组合，外层遍历金额是排列。如果题目要求组合数而写成排列，结果会偏大。判断方法是在草稿上用两个不同顺序的面额各手动数一遍，比如硬币1、2凑3元，组合数只有两种，排列数会有重叠。一旦发现答案含有“1+2”和“2+1”这种顺序相反的计数，就要调整循环层级。

7.6 复杂度失控以后怎么救

动态规划不是万能钥匙，状态数过于庞大时同样会超时或超空间。比如0-1背包容量非常大而物品数量很小，二维DP就扛不住，这时可以考虑把“价值”作为DP维度，求“达到某个价值需要的最小容量”，再用总容量去比较。找零钱如果硬币面额很少但金额巨大，可以考虑用贪心配合DP剪枝，不过这类优化对初学者偏难，不建议一上来就走偏门。先把最标准的写法练熟，遇到优化需求时再针对状态维度动手。

我个人在实际操作中还有一个很笨但有效的习惯：每学一个DP问题，就把它的“状态定义”“转移方程”“边界条件”“常见变体”写成一张卡。卡不用很长，但必须用自己的话写清楚。学完这六个问题再回头看，你会发现它们本质上只有两件事：一是把问题压缩成几个关键参数，二是明确每一步有哪些选择。参数决定状态表的长相，选择决定转移方程的写法。想通这两点，后面再遇到区间DP、树形DP、状态压缩DP，上手速度会快很多。