综述

本质理解为：有限集中的最值求解。

分析问题分为两个阶段：

1. 状态表示：化零为整

   每次枚举一个有相似性的子集，用一个状态$f_i$来表示。

   1. 整体的优化表示在每次按集合考虑
   2. 属性：$Max/Min/Count$

2. 状态计算：化整为零

   集合划分要求不重复、不遗漏；求每一个子集。

   如：$\max(\{{A,B,C,D}\})=\max(\{A_{\max},\cdots)$

划分依据：寻找最后一个不同点

动态规划大都是经验题目，需要同类型题目的练习。

例题

01背包问题

$N$物品，$V$容量，每个物品只能用一次；体积$v_i$，价值$w_i$，求最大重量。

分析：有限求值问题→有限集合的求值问题，找到$2^n$个情况中最大的。

暴力朴素方法：枚举$2^n$个情况。

1. 状态表示$f(i,j)$

   1. 集合：所有只考虑前$i$个物品，而且体积不超过限制的集合。
   2. 属性：集合当中每一个方案的最大价值。$f(N,V)$即为答案。

2. 状态计算：寻找最后一个不同点

   1. 子集划分：[所有不选择第$i$个物体的方案，所有选择第$i$个物体的方案]
      1. 所有不选择第$i$个物体的方案：$f(i-1,j)$
      2. 变化的部分的值(前面已经选择了的物品的重量)+不变的部分的值(当前物品重量) = $f(i-1,j-v_i)+w_i$
   2. 求值：$\max(f(i-1,j),f(i-1,j-v_i)+w_i)$

   注意有时候子集可以是空的，如不满足重量情况时子集为空。

得到状态转移方程：$f(i,j)=\max(f(i-1,j),f(i-1,j-v_i)+w_i)$

**进一步优化：**空间优化。

观察得知，每次只用到一次$i$，故可以用滚动数组，省一维储存空间。