DP 概述

Vision271 · 2022-11-03 21:44:59 · 个人记录

（施工初期，只放了一点想法）

• DFA

本质要求

• 递推性

• 最优子结构

• 无后效性/DAG/拓扑序

——————

实践法则

• 极小状态集

• 优化转移

LCA

• 下面打引号的都是 LCA 原话，括号里也是，除非括号里有 注： 。

• “dp 的一个理解是，假设 T 是一个判定单一方案的自动机，那么设f(i,S) 表示使得输入 i 时刻后使得自动机 T 的状态（内存）为 S 的所有方案的解（注：这里也许应该是“所有方案的解的并”，当然这种并只是一种结合罢了）（比如最大权值）。”

• 不妨以 01 背包求最大总价值为例，此时 T 是一个如下的程序（已经将判定合法性改成了判定+计算）：

  int valuesum=0,sizesum=0;
  for i=1 到 n，如果方案第 i 位是 1 
  sizesum+=size[i],valuesum+=value[i]
  如果 sizesum 大于总容量，return -1 表示不合法
  否则无事发生
  循环结束后
  如果 sizesum 大于容量，return -1 表示不合法
  否则 return valuesum

• “总之，对于组合决策问题（也就是处理可能方案的问题），如果有判定算法 T，并且 f(T) 存在递推，就有对应的状态压缩最优化/计数/算法 F(T)，称为T的状态压缩递推算法”

• “f(i,S) 表示使得输入 i 时刻后使得自动机 T 的状态为 S 的所有方案的解（如果采用 S 内含计数器（注：指自动机内的状态有‘走了几步’或‘经过多久’这个信息）的计算模型，就简化成f(S)）（注：f 就是 dp 本身），然后 f(T) 就是 f(S)（注：或者 f(i,S)） 这个函数，F(T) 是基于递推 f(T)（注：f(T) 的可递推性，或者说 f(T) 的递推方式）的算答案的算法（注：F(T) 是 dp 程序本身）”。

• dp 套 dp 大体上就是“问题可以拆成两层组合决策，T_1 是判定“两个数是不是都在区间范围内”的，T_2 是判定“一个 and 结果是否存在可能方案”的。这里，T_2=F(T_1)，所以整个题是 F(F(T_1))”（注：题目是当时的，显然 T_1,T_2 是可变的，dp 套 dp 的重点是两者之间的关系）。