← 背包问题九讲 · 动态规划的思考艺术 / 问法变化:换聚合算子即换问法 待审核 9 / 10
Ⅸ · 问法变化 · max → min / sum / OR

问法变化:换聚合算子即换问法

前八讲都在问「最大价值」。但同一组数据、同一个状态骨架 F[v]F[v],可以提出多种不同的问题:最少用几件?有多少种凑法?能否恰好凑出?第 K 优解是多少?这些几乎不需要改算法。关键只有一句:状态不变,只替换转移里的聚合算子——max 换成 min / sum / OR,再配上对应的初值。下面用一个 tab 切换四种问法,观察 F 数组随之变化。

1 · 四种问法的并列对照

同一组硬币与目标金额,四种问法切换:最大价值 / 最少件数 / 方案数 / 可行性。观察 F 数组的形态如何随问法变化——状态骨架不动,变的只是聚合算子(max / min / sum / OR)与初始化语义。其中「方案数」与「最少件数」在第 2 讲(完全背包) §4 / §5 已作为具体变形出现,本讲把它们纳入统一框架。

元洞察 · 终章。 DP 的本质是「状态空间 + 转移聚合」。聚合方式可以是 max / min / sum / count / 队列合并。换聚合 = 换问题——这是从「解题模板」跨越到「DP 抽象」的关键一步。