跳到主要内容
约 27 分钟10 张卡

动态规划

动态规划(Dynamic Programming,DP)把重复出现的子问题的答案存下来,再按依赖顺序把它们组合成更大问题的答案。同一个子问题只算一次,原本指数级的搜索往往就能降到多项式时间。

DP 题的难点不在写循环,而在想清楚「一个状态到底代表什么」。状态定义对了,转移、初始化和计算顺序基本都能顺着推出来;定义错了,代码怎么调都不对。设计时可以依次回答这五个问题:

  1. 哪些信息会影响后续选择,需要保存在状态中?
  2. 当前状态能由哪些合法操作得到?
  3. 空输入和不可达状态怎样初始化?
  4. 按什么顺序计算,才能读到需要的旧结果?
  5. 压缩空间后,怎样恢复具体方案?

1. 面试核心​

先记住这几条,再读正文
  • 状态必须包含决定后续合法选择的全部信息。只有后续选择和目标值都相同的子问题,才能共用一个状态的结果。
  • 限制交易次数时,明确一次交易在哪个动作完成,并区分状态中的恰好次数与答案要求的至多次数。卡 · 交易次数限制
  • 编辑距离用两个字符串的前缀长度定义状态,末尾字符不同时,比较插入、删除和替换三种来源。卡 · 编辑距离
  • 最长公共子序列允许跳过字符,公共子串则要求字符连续,所以两者的状态和答案位置不同。卡 · 最长公共子序列
  • 严格 LIS 以当前位置结尾保存长度,最大子数组则以当前位置结尾保存连续和;全局答案都要比较所有结尾位置。 卡 · 最长严格递增子序列卡 · 最大子数组和与区间
  • 相邻天不能重复活动时,保留最后一天的活动种类,三个新状态都从上一天读取。卡 · 相邻天活动限制
  • 初值由状态含义推出:计数 DP 把空方案算作一种时初值为 1,不可达状态要用区别于合法零值的标记表示。
  • 二叉搜索树计数按根划分,左右方案数相乘、各根结果相加,空树计数为 1。卡 · 二叉搜索树数量
  • 背包压成一维数组后,0/1 背包按容量倒序更新,完全背包按容量正序更新。卡 · 计算顺序
  • 业务约束决定状态和可行规模;预算内独立方案选择可映射到 0/1 背包,预算取值大时仍要评估 O(nB) 成本。卡 · 预算内方案选择
  • 求最少项数组合时,保存最后一次选择就能回退恢复方案;不可达与零目标的空方案必须区分。卡 · 最少项数组合

2. 适用信号​

DP 的收益来自复用子问题的结果,所以先要确认问题里真的有可复用的东西。出现下面这些信号时,可以考虑用 DP 建模:

  • 问题求的是最优值、方案数或能否到达。
  • 大问题能拆成规模更小的同类问题。
  • 暴力递归时,相同的参数组合被反复计算,这叫重叠子问题。
  • 当前选择对未来的影响,能用有限的几项信息概括。

求最优值的问题还需要最优子结构:原问题的最优解能由子问题的最优解组合出来。反过来,如果子问题几乎不重复,存下结果也省不了多少计算。

有两种情况不必用 DP。题目要求列出全部方案时,生成这些方案本身的成本省不掉,通常用回溯。能证明每一步的局部选择始终安全时,用更简单的贪心就够了。

3. 状态设计​

状态是对「走到这一步时,影响后续的全部信息」的概括。设计状态,就是回答哪些不同的历史可以共用同一个子问题的答案。动手写代码前,先用一句话把它定义出来:

dp[i][s] 表示处理到位置 i、处于条件 s 时的最优值或方案数。

这句话要写清三件事:处理到哪里,处于什么约束下,存的值是什么。以买卖股票为例,如果只记录「第 i 天的最大利润」,就漏掉了是否持股:持股时才能卖,不持股时才能买,后面能做的动作完全不同,两种情况不能共用一个结果。

本文的股票例子允许多次交易,最多同时持有一股,没有手续费和冷冻期。状态这样定义:

cash[i] = 第 i 天结束时,未持股的最大利润
hold[i] = 第 i 天结束时,持有一股的最大利润

规则变了,状态就要跟着变。限制交易次数时,状态里要加上剩余次数;有冷冻期时,要区分当前能不能买入;有手续费时,状态不变,只在买卖的转移里扣掉费用。原则是只保留影响未来的条件:不影响后续选择的历史细节都可以丢掉,这样不同的历史才能合并到同一个子问题。

3.1 交易次数限制​

限制为至多 k 笔交易时,需要把已经完成的卖出次数放进状态;一次买入再卖出才算完成一笔交易。仍约定最多持有一股、价格非负、没有手续费和冷冻期,每天至多进行一次买入或卖出。设 cash[i][t]、hold[i][t] 分别表示第 i 天结束、恰好完成 t 次卖出时不持股和持股的最大利润:

cash[i][t] = max(cash[i-1][t], hold[i-1][t-1] + price[i]) // t >= 1 才能卖出
hold[i][t] = max(hold[i-1][t], cash[i-1][t] - price[i]) // t < k 才有必要再买

买入不增加 t,卖出才增加。开始前一天只有 cash[-1][0]=0 可达,其余状态都不可达;读取不可达前驱时跳过这条转移,不能直接对哨兵做加减。每一天都从上一天读取,t 的范围是 0 到 k。t 为 0 的 cash 只能沿用上一天,t 为 k 时不再开启新交易。

状态里用“恰好”区分历史,最终要求“至多”时,答案取最后一天所有 cash[t] 的最大值,包含 t=0 的不交易方案;如果题目要求恰好 k 笔,则只看 cash[k],还要判断它是否可达。k=0 或没有交易日时,至多交易的答案为 0。完整计算需要 O(nk) 时间,按天滚动后用 O(k) 空间。面试只说“股票买卖”或“最简单版”时,不能据此判断究竟是一笔还是不限次数,应先问清限制。

4. 状态转移​

状态转移说明当前状态的答案怎样由已经算好的状态得到。推导时,从「到达当前状态的最后一个动作」入手,把所有合法来源都列出来。股票例子的转移如下:

cash[i] = max(cash[i-1], hold[i-1] + price[i])
hold[i] = max(hold[i-1], cash[i-1] - price[i])

今天结束时不持股,要么昨天就不持股、今天什么都没做,要么昨天持股、今天卖掉了,cash[i] 取两者的较大值。今天结束时持股同样有两种来源:继续拿着昨天的股票,或者昨天不持股、今天买入。

按最后一步分类的好处是容易检查有没有漏掉来源。每条转移还要符合题目规则,比如不能在已经持股时再买一股。

4.1 编辑距离​

编辑距离是把字符串 A 变成字符串 B 所需的最少操作次数,允许插入、删除和替换一个字符,每次操作成本为 1。

两个完整字符串不好直接比较,我们改为比较它们的前缀(从开头截取的一段)。设 dp[i][j] 为 A 的前 i 个字符变成 B 的前 j 个字符所需的最少操作数,转移只看两个前缀的末尾字符。两串要用同一种字符单位比较:

若 A[i-1] == B[j-1]:dp[i][j] = dp[i-1][j-1]
否则:dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
dp[0][j] = j,dp[i][0] = i

末尾字符相等时,这个字符原样保留,不需要操作,答案就是两个前缀各去掉末尾后的结果,也就是表格左上角的 dp[i-1][j-1]。末尾不同时,最后一步必然是下面三种操作之一,取三者最小值再加 1:

  • 删除 A 的末尾字符,来自 dp[i-1][j]。
  • 在 A 的末尾插入 B 的末尾字符,来自 dp[i][j-1]。
  • 将 A 的末尾字符替换成 B 的末尾字符,来自 dp[i-1][j-1]。

边界来自空串:空串变成长度为 j 的前缀要插入 j 次,长度为 i 的前缀变成空串要删除 i 次。举个例子,cat 变成 cut 只需把 a 替换成 u,距离是 1。

两串长度为 m、n 时,表格有 (m+1)(n+1) 格,时间和空间都是 O(mn)。如果只要距离、不要具体操作,当前格只依赖上一行和当前行的左侧,保留两行就够了,空间降到 O(n)。

下面把递推直接写成二维表。这里约定两个参数都不能为 null,编辑单位是 Unicode 码点;codePoints() 会把一对合法的 UTF-16 代理项合成一个码点。它不做 Unicode 规范化,也不把多个码点组成的可见字符视为一个单位。这些是示例的接口约定,题目未说明字符单位时应先确认。

static int editDistance(String a, String b) {
java.util.Objects.requireNonNull(a);
java.util.Objects.requireNonNull(b);
int[] x = a.codePoints().toArray();
int[] y = b.codePoints().toArray();
int[][] dp = new int[x.length + 1][y.length + 1];
for (int i = 0; i <= x.length; i++) dp[i][0] = i;
for (int j = 0; j <= y.length; j++) dp[0][j] = j;
for (int i = 1; i <= x.length; i++) {
for (int j = 1; j <= y.length; j++) {
if (x[i - 1] == y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[x.length][y.length];
}

editDistance("cat", "cut") 返回 1,editDistance("", "😀") 也返回 1,因为后者是插入一个码点。空串仍需保存边界行或列,所以包含空输入时,更完整的时间和空间写法是 O((m+1)(n+1)),m、n 为码点数;另有 O(m+n) 的码点数组。二维表适合规模可容纳于内存的输入,长文本应根据是否需要恢复编辑过程选择空间压缩。

4.2 最长公共子序列​

子序列是从字符串里删掉若干字符、保持剩余字符顺序得到的序列,它允许跳过字符。最长公共子序列(LCS)是两个字符串共有的最长子序列。设 dp[i][j] 为 A 的前 i 个字符与 B 的前 j 个字符的 LCS 长度:

若 A[i-1] == B[j-1]:dp[i][j] = dp[i-1][j-1] + 1
否则:dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp[0][j] = dp[i][0] = 0

两个末尾字符相等时,把它接在两个更短前缀的公共子序列后面,长度加 1。不相等时,这两个末尾字符不可能同时出现在公共子序列的末尾,至少要跳过一个,所以取上方 dp[i-1][j] 和左方 dp[i][j-1] 中的较大值。任一前缀为空时,长度为 0。

比如 abc 和 ac 的结果是 2,跳过 b 后得到 ac。时间和空间都是 O(mn),m、n 是两串长度。

最长公共子串不同,它要求字符连续,不能跳过。所以状态要改成「以 A 的第 i 个字符和 B 的第 j 个字符结尾的连续匹配长度」:末尾不相等时,连续匹配中断,状态直接归零。最长的那段匹配可能在任意位置结束,答案要取全表的最大值,而不是右下角。

4.3 最长严格递增子序列​

最长严格递增子序列(LIS)是在保持原顺序的前提下,选出尽量多的数,使后一个数严格大于前一个。它只处理一个序列,与比较两个序列的 LCS 是不同问题。[3,1,2,2,4] 可以选 [1,2,4],长度为 3;相等的两个 2 不能同时接入严格递增序列。

设 dp[i] 为以 nums[i] 结尾的最长严格递增子序列长度。只选它自己就有长度 1;再枚举 i 之前的 j,只有 nums[j] < nums[i] 时才能接在 j 后面,候选长度为 dp[j]+1。每一种以 i 结尾的多元素方案都有倒数第二个位置 j,因此枚举这些 j 不会漏解。答案取所有 dp[i] 的最大值,不一定在最后一个位置。

static int lisLength(int[] nums) {
java.util.Objects.requireNonNull(nums);
int[] dp = new int[nums.length];
int best = 0;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
best = Math.max(best, dp[i]);
}
return best;
}

代码拒绝 null,空数组返回 0,[2,2,2] 返回 1,负数也能直接比较。时间 O(n²),辅助空间 O(n)。只说“递增”而没有说明严格性时,应先确认相等值能否相邻;若要求最长非降子序列,比较条件改成 <=,结果就可能不同。

4.4 最大子数组和与区间​

最大子数组和是在所有非空连续片段中找出最大的元素和。连续性意味着,以位置 i 结尾的最优片段只有两种来源:把 nums[i] 接到前一个片段后,或者从 i 重新开始。因此 ending[i]=max(nums[i], ending[i-1]+nums[i]),全局答案再取所有结尾位置的最大值。

恢复区间只需要额外记住当前片段的起点。前一个片段的和小于 0 时,接上它只会降低当前和,所以从 i 重新开始;否则保留原起点。全局最优值变大时,同时保存这次的起点和终点。

record Subarray(long sum, int from, int toExclusive) {}

static Subarray maxSubarray(int[] nums) {
java.util.Objects.requireNonNull(nums);
if (nums.length == 0) throw new IllegalArgumentException("nonempty array required");
long ending = nums[0], best = nums[0];
int start = 0, bestStart = 0, bestEnd = 1;
for (int i = 1; i < nums.length; i++) {
if (ending < 0) {
ending = nums[i];
start = i;
} else {
ending += nums[i];
}
if (ending > best) {
best = ending;
bestStart = start;
bestEnd = i + 1;
}
}
return new Subarray(best, bestStart, bestEnd);
}

返回区间使用左闭右开 [from,toExclusive),这是本例的接口约定。[-2,1,-3,4,-1,2,1,-5,4] 返回和 6、区间 [3,7),对应 [4,-1,2,1]。[-3,-1,-2] 返回和 −1、区间 [1,2),所以初值必须来自第一个元素,不能用 0 暗中允许空片段;本例拒绝 null 和空数组。

并列时约定先选结束位置最早的片段,再选起点最早的片段:只有 ending > best 才更新全局答案,前缀和为 0 时继续延长。累计值用 long,Java int[] 的长度和每项都是 int 范围,任意片段的和都可放入 long;若接口改收任意 long 元素,就要另行检查溢出。总时间 O(n),辅助空间 O(1)。

4.5 相邻天活动限制​

每天必须从三种活动中选一种、相邻两天不能相同时,最后一天选了什么决定下一天的合法选择。只保留“截至今天的最大收益”会丢掉这个条件。设 dp[i][a] 为第 i 天选择活动 a 时,前 i+1 天的最大累计收益:

dp[i][a] = reward[i][a] + max(dp[i-1][b]),其中 b != a
dp[0][a] = reward[0][a]

每一天的三个新状态都从前一天读取,不能算完今天的 A 后,立即拿它去算今天的 B。下面用三个临时变量保留这一轮的新结果:

static long maxActivityReward(int[][] reward) {
java.util.Objects.requireNonNull(reward);
for (int[] row : reward) {
if (row == null || row.length != 3) {
throw new IllegalArgumentException("three rewards per day required");
}
}
if (reward.length == 0) return 0;
long a = reward[0][0], b = reward[0][1], c = reward[0][2];
for (int day = 1; day < reward.length; day++) {
long nextA = Math.max(b, c) + reward[day][0];
long nextB = Math.max(a, c) + reward[day][1];
long nextC = Math.max(a, b) + reward[day][2];
a = nextA;
b = nextB;
c = nextC;
}
return Math.max(a, Math.max(b, c));
}

收益表 [[10,40,70],[20,50,80],[30,60,90]] 返回 210,选择 C、B、C 得到 70+50+90。本例另作教学约定:收益可以为负,0 天返回 0,每行恰有三项,null 输入或无效行被拒绝。非空时每天必须选一种,因此 [[−3,−1,−2]] 的结果是 −1,不能用“不选”的 0 覆盖它。累计收益用 long,对 Java int[][] 的天数和整数收益范围足够;时间 O(n),辅助空间 O(1)。

5. 初始化​

初始化是给最小的子问题直接填上答案,后续转移才有起点。初值不是随手填 0,而要从状态的含义推出来。几种典型情况:

  • 计数问题若存在一个空方案,初值就是 1。
  • 恰好装满背包时,只有容量 0 初始可达,其余容量先标记为不可达。
  • 容量只要求不超过上限、收益非负时,可以用“不选物品”的收益 0 初始化。
  • 网格路径要处理第一行、第一列的前驱边界,也可在表外加一圈辅助位置来统一转移。

表示不可达的特殊值叫哨兵值,它用来把「没有方案」和合法答案区分开。哨兵值参与运算前,要先判断状态是否可达。比如用 Long.MIN_VALUE 表示负无穷,减去一个正数会溢出成很大的正数;加上一个正数虽然不溢出,却会得到一个看起来正常的有限值,不可达状态就被误当成了合法方案。

另一种做法是在确认运算范围后,用 Long.MIN_VALUE / 4 这样的有限负值留出运算余量。但这只解决溢出问题,仍要保证它和合法收益区分得开,不可达的转移也不能被当成有效结果。

股票例子可以绕开哨兵值,直接按第一天的情况初始化:不持股利润为 0,持股利润是买入价的相反数:

static long maxProfit(int[] prices) {
if (prices.length == 0) return 0;
long cash = 0;
long hold = -(long) prices[0];
for (int i = 1; i < prices.length; i++) {
long previousCash = cash;
cash = Math.max(cash, hold + prices[i]);
hold = Math.max(hold, previousCash - prices[i]);
}
return cash;
}

这段代码假定价格非负。[3,1,4] 返回 3,对应价格 1 时买入、价格 4 时卖出;空数组直接返回 0。每个交易日只更新两个变量,时间是 O(n),辅助空间是 O(1)。

5.1 二叉搜索树数量​

使用互不相同的键 1 到 n 构造二叉搜索树时,根的取值确定了左右子树各有多少节点。选 r 为根,左边只能放 1 到 r−1,右边只能放 r+1 到 n。每一种左子树都可以与每一种右子树组合,所以固定根时两侧方案数相乘;不同根产生不同的树,再将各根的方案数相加。

设 count[n] 为 n 个互异有序键能构成的树形数量。具体键值不会改变树形数,只有相对顺序和节点数有影响:

count[n] = sum(count[left] * count[n-1-left]),left 从 0 到 n-1
count[0] = 1

空树算一种,是为了让“左边为空、右边有一种树”仍能组合出一种结果;如果空树计数为 0,任何带空孩子的组合都会被错误消掉。

static long countBsts(int n) {
if (n < 0 || n > 19) throw new IllegalArgumentException("0 <= n <= 19 required");
long[] count = new long[n + 1];
count[0] = 1;
for (int size = 1; size <= n; size++) {
for (int left = 0; left < size; left++) {
count[size] += count[left] * count[size - 1 - left];
}
}
return count[n];
}

countBsts(3) 返回 5:左右规模分别为 (0,2)、(1,1)、(2,0),贡献为 2+1+2。代码采用 LC96 的 n≤19 范围,并为递推边界额外允许 n=0;countBsts(19) 为 1767263190,long 足以容纳范围内的乘积和总数。更大 n 不能直接沿用这个数值保证,应估算上界或使用 BigInteger。时间 O(n²),辅助空间 O(n),无需生成每一棵树。

6. 计算顺序​

计算顺序要保证两点:读取一个状态时,它已经算好了,而且存的还是转移需要的那一轮结果。dp[i] 依赖 dp[i-1] 时按 i 递增计算;二维网格依赖左方和上方时,按行、列递增即可。

第二点在一维背包里最容易出错。0/1 背包规定每件物品最多用一次。把二维表压成一维数组后,处理第 i 件物品时,转移要读的是「还没考虑这件物品」的上一轮结果:

for (int i = 0; i < weights.length; i++) {
for (int c = limit; c >= weights[i]; c--) {
dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
}
}

这里 weights 都是正整数,values 是非负收益,dp[c] 表示容量不超过 c 时的最大收益,初值全为 0。容量从大到小更新时,比 c 小的位置还没被当前物品更新过,dp[c - weights[i]] 读到的仍是上一轮的值,所以当前物品最多被加入一次。

用一个反例看正序为什么错:只有一件重量 2、收益 3 的物品,容量为 4,正确答案是 3。正序更新会先写入 dp[2]=3,算 dp[4] 时又读到这个新值,得到 dp[4]=6,同一件物品用了两次。完全背包允许同一物品重复使用,正好需要这种效果,所以它按容量正序更新。循环方向由状态依赖决定,解释时要和状态含义一起讲。

6.1 预算内方案选择​

业务约束能否对应一个可计算的状态,比给问题贴上“动态规划”的名字更重要。假设要从候选推广方案中选一批:每个方案最多执行一次,成本是正整数,预估收益是非负整数,总预算不超过 B,收益可相加且方案之间没有互斥或依赖。这是一个用于说明建模的简化业务例子。

令 dp[i][b] 表示只考虑前 i 个方案、预算上限为 b 时的最大预估收益。第 i 个方案要么不选,沿用 dp[i-1][b];要么选,在成本不超过 b 时比较 dp[i-1][b-cost[i]]+gain[i]。预算只是上限,空方案收益为 0,因此初值为 0,最后读取 dp[n][B];压成一维后就是上面的倒序容量循环。

例如预算 5,三个方案的 (成本,收益) 分别为 (2,3)、(3,4)、(4,5),选择前两个得到 7,高于只选第三个的 5。模型需要 O(nB) 时间、压缩后 O(B) 空间,成本取值很大时,按金额建表未必合适;还要按收益总和选择数值类型。如果两个方案组合后收益不再可加,或者必须配套执行,现有转移就不成立,必须重新表达这些约束,不能直接把背包模板套到实际系统里。

7. 自顶向下与自底向上​

同一组状态和转移,既可以用递归从目标往下求,也可以从最小问题开始按顺序填表。两者算的是同一批状态,区别在于从哪里出发、怎样安排计算顺序。

7.1 记忆化搜索​

记忆化搜索从目标状态开始递归,算过的结果存进缓存,再次遇到时直接取用。它只计算实际用到的状态,而且容易从暴力递归改出来;代价是递归太深时可能栈溢出。

缓存的键要包含完整的状态,表示「还没算」的标记也要和合法答案区分开,具体见递归。

7.2 表格递推​

表格递推按依赖顺序用循环填表,没有递归调用栈,也方便做空间压缩。即使最后写成表格,也可以先写出递归关系,用它检查状态和来源是否完整。

只要每个状态只求一次,两种方式的时间都等于所有转移工作的总和。每条转移是 O(1) 时,时间可以用「状态数 × 每个状态的转移数」来估算,比如编辑距离有 O(mn) 个状态、每个 3 条转移,总共 O(mn)。

8. 空间压缩​

空间压缩是把已经用不到的旧结果覆盖掉,减少同时保存的状态。压缩之前,先把完整的状态写清楚,再确认每个旧值最后一次在哪里被读取,确认它用完了才能覆盖。

常见的几种压缩方式:当前行只依赖上一行时,用两行数组轮流使用;只依赖几个值时,用几个变量滚动更新。LCS 压成一行时,左上角的旧值会先被覆盖,要用一个变量提前存下来。背包则靠循环方向保证读到的是上一轮还是本轮的结果。

股票例子里的 previousCash 存的是昨天的 cash。在本文无手续费、无冷冻期的模型里,直接用更新后的 cash 其实也能得到相同结果,因为同一天卖出再买回,持股利润不会变高。保留旧值是为了让代码和递推式一一对应,交易规则一变,也更容易核对。

压缩的代价是状态的读取顺序更难看出来,恢复具体方案所需的前驱信息也被覆盖了。如果要返回具体选择,可以另外记录每一步的决策,或者保留完整的表再倒推,也可以按需重新计算。面试时先讲清完整状态,再说明哪些结果已经用完、可以覆盖。

8.1 最少项数组合​

从一组数中重复选择若干项,使总和恰好为 target,既要项数最少,又要输出一种组合。下面先约定可选值都是正整数、target 是非负整数;若题目未给出符号和范围,这只是教学模型,需要先向面试官确认。含负数时,不能把所有中间和直接限制在 0 到 target。

令 count[sum] 为恰好组成 sum 的最少项数,count[0]=0,其余先标记不可达。枚举最后选的值 value,只从可达的 sum-value 转移,候选项数为 count[sum-value]+1。所有 value 为正,前驱严格更小,所以 sum 递增时已经算好了。每次找到更优答案,额外记住 last[sum]=value;求完后从 target 反复减去 last,就能恢复最少项数的一种组合。

static java.util.Optional<java.util.List<Integer>> minCombination(int[] values, int target) {
java.util.Objects.requireNonNull(values);
if (target < 0 || target == Integer.MAX_VALUE) {
throw new IllegalArgumentException("0 <= target < Integer.MAX_VALUE required");
}
for (int value : values) {
if (value <= 0) throw new IllegalArgumentException("positive values required");
}
int[] count = new int[target + 1];
int[] last = new int[target + 1];
java.util.Arrays.fill(count, -1);
count[0] = 0;
for (int sum = 1; sum <= target; sum++) {
for (int value : values) {
if (value <= sum && count[sum - value] != -1) {
int candidate = count[sum - value] + 1;
if (count[sum] == -1 || candidate < count[sum]) {
count[sum] = candidate;
last[sum] = value;
}
}
}
}
if (count[target] == -1) return java.util.Optional.empty();
java.util.List<Integer> result = new java.util.ArrayList<>();
for (int sum = target; sum > 0; sum -= last[sum]) result.add(last[sum]);
return java.util.Optional.of(result);
}

values=[1,3,4]、target=6 时返回 [3,3],项数为 2;按最大值优先拿到的 [4,1,1] 并非最优。values=[2]、target=3 返回空 Optional 表示无解,target=0 则返回包含空列表的 Optional,表示有一个不选任何项的有效方案。相同项数时保留第一次找到的来源,返回任意一个最优组合,不承诺字典序;重复面值不影响最少项数。

设可选值数量为 m,目标为 T,状态转移需要 O(mT) 时间,另有 O(m+T) 的输入校验、数组初始化和按目标和推进的开销;恢复方案最多需要 O(T) 时间。数组空间为 O(T+1),返回列表最多 T 项。代码拒绝 null、非正面值、负目标以及会使 target+1 溢出的最大 int;这只保证索引与计数运算的范围,实际 T 还必须能被时间和内存预算接受。恢复时每次总和严格减小,且每个可达正数状态都记录过 last,所以会回到 0。

固定面值 1、3、5、10 兑换 100 则可以直接证明:每枚最多贡献 10,至少需要 10 枚;十枚 10 正好达到下界。这不代表任意面值都能贪心,面值一变就需要重新证明,或用上述通用递推。

9. 转移完整性​

转移式写出来以后,还要确认它没有漏掉合法方案,也没有算进非法方案。可以逐项核对这五个条件:

  1. 状态覆盖:每个合法解都能由某个终态表达。
  2. 来源完整:到达当前状态的最后一步,都落在列出的转移中。
  3. 来源合法:每条转移都满足题目约束。
  4. 无后效性:状态保留的信息足以决定未来,省略的历史不再影响后续选择。
  5. 计算有序:前驱已经计算完成,读取的是转移要求的那一轮结果。

哪一项说不清楚,就回到状态定义和转移重新推导。另一个实用的办法是写一个暴力穷举,在小规模输入上和 DP 结果对拍,检查有没有漏算或多算。

树上的状态还要区分“整棵子树里的最优答案”与“能继续接到父节点的结果”。例如二叉树最大路径和在节点处可以合并左右两臂,向父节点却只能返回单臂,否则路径会分叉。具体机制与实现见树与图搜索。

10. 常见问题​

10.1 动态规划和贪心有什么区别?​

DP 保留多个状态,比较所有合法来源再取最优;贪心每一步只保留一个局部选择,所以必须证明舍弃其他选择是安全的。同一个问题可能既有 DP 解法也有贪心解法,贪心的证明方法见贪心。

10.2 状态维度是不是越多越保险?​

10.3 只算出了最优值,怎样还原具体方案?​

10.4 方案数太大,用什么类型存?​

11. 面试题卡片​

12. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明