算法课9-dynamic programming II

背包问题串讲

背包问题没有办法用贪心法得到最优解，都是通过动态规划来实现最优解。只有gold dust模型可以用贪心法得到最优解（性价比最高实现）。

1. 0-1背包问题【每个物品只可以拿一次】
   
   OPT(i, w) = max profit subset of items 1, …, i with weight limit w.
   它是伪多项式时间的解法，NPC问题
   解释看这里 0-1背包为什么有多项式时间解法
   空间优化方法：
   $opt(w)=max(opt(w),opt(w-w_i)+v_i)$opt(w)=max(opt(w),opt(w−wi​)+vi​)
   因为每次需要使用上一次的值，所以扫描W时，需要从大到小扫，这样大的值所用的就是i-1时候的值了。

2. 完全背包问题【每个物品可以拿无限次】
   
   与0-1背包的不同之处在于下面是OPT(i,w-w_i) 是用更新过后的值。在初始化时多了将W=0也初始化为0的步骤。
   空间优化方法：
   $opt(w)=max(opt(w),opt(w-w_i)+v_i)$opt(w)=max(opt(w),opt(w−wi​)+vi​)
   与0-1背包式子相同，但由于每次用到第i次的值，扫描W就应当从左向右扫。
   在空间优化后想要知道用了什么物品，可以通过一维数组在对应位置存储引起状态变化的i，在最后一次循环完成后进行回溯。而0-1背包在空间优化后无法知道用了什么物品，因为首先更新的是W较大的值，会把之前的值都覆盖掉。

3. 完全背包问题-背包恰好被装满
   每次要么不选，要么把背包恰好装满的最大值，递推公式和完全背包问题相同，不同的是，初始化时，OPT(0,0)=0,OPT(0,W)=$-\infin$−∞是非法解，求解过程可以用负数来标记非法解。

4. 多重背包问题
   物品有数量限制，一种方法是把多个同种物品看成不同物品然后用0-1背包
   还有一种方法是对数量进行拆分，例如1024个物品，可以拆成1，2，4，8…1024个物品，这样可以凑成任意自然数的和。

RNA二级结构问题

二维动规加遍历问题
四个规则：
①U-A C-G
② 末端不允许出现尖角，位置i和j配对，那么$i\leq j-4$i≤j−4
③每个核苷酸只能参与一次配对
④不允许交叉
给定RNA链，求最多匹配数


formula 即 $OPT(i,j)=max(OPT(i,j-1),max_t(1+OPT(i,t-1)+OPT(t+1,j-1)))$OPT(i,j)=max(OPT(i,j−1),maxt​(1+OPT(i,t−1)+OPT(t+1,j−1)))
类比问题：矩阵乘法加括号
dp方法论-矩阵乘法加括号