问法变化:换聚合算子即换问法
前八讲都在问「最大价值」。但同一组数据、同一个状态骨架
,可以提出多种不同的问题:最少用几件?有多少种凑法?能否恰好凑出?第 K 优解是多少?这些几乎不需要改算法。关键只有一句:状态不变,只替换转移里的聚合算子——max 换成 min / sum / OR,再配上对应的初值。下面用一个 tab
切换四种问法,观察 F 数组随之变化。
1 · 四种问法的并列对照
同一组硬币与目标金额,四种问法切换:最大价值 / 最少件数 / 方案数 / 可行性。观察 F 数组的形态如何随问法变化——状态骨架不动,变的只是聚合算子(max / min / sum / OR)与初始化语义。其中「方案数」与「最少件数」在第 2 讲(完全背包)
§4 / §5 已作为具体变形出现,本讲把它们纳入统一框架。
元洞察 · 终章。 DP 的本质是「状态空间 + 转移聚合」。聚合方式可以是 max / min / sum / count / 队列合并。换聚合 = 换问题——这是从「解题模板」跨越到「DP 抽象」的关键一步。