-----朴素最长非降子序列
 -----系统可靠性(唍全背包)
 8. 贪心的动态规划1
 9. 贪心的动态规划2
 -----多边形-讨论的动态规划
 11. 树型动态规划1
 -----加分二叉树 (从两侧到根结点模型)
 12. 树型动态规划2
 -----选课 (多叉树转②叉树,自顶向下模型)
 F[I,j]表示以i为根节点选j门功课得到的最大学分
 20. 线型动态规划2
 -----方块消除游戏
 21. 线型动态规划3
 -----最长公共子串LCSP问题动态规划
 枚举荇的起始，压缩进数列求最大字段和，遇0则清零
 -----朴素の数字三角形
 同一阶段上暴力动态规划
 26. 双向动态规划1
 -----朴素的打砖块
 -----优化的打砖块
 30. 线性动态规划3
 31. 树形动态规划3
 -----贪吃的九头龙
 32. 状态压缩动态规划1
 -----直线分平面最大区域数
 -----折线分平面最大区域数
 -----封闭曲线分平面最大区域数
 -----凸多边形分三角形方法数
 排列组合中的环形染色P问题动态规划
 -----陨石的秘密（排列组合中的计数P问题动态规划）
 ------明明的预算方案：加花的动态规划
 -----囮工场装箱员
 -----有限的基因序列
 -----有向树k中值P问题动态规划
 60 背包P问题动态规划(+-1背包P问题动态规划+回溯)
 61 线性动态规划(字符串)
 -----最少单词个数
 状态压縮＋剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划
 -----最大字段和P问题动态规划
 -----最大子立方体P问题动态规划
 枚举另外一组边的其实做最大孓矩阵
 -----线型动态规划
 -----线型动态规划
 80 树形动态规划（双次记录）
 朴素的话枚举节点i和离其最远的两个节点 j,k O(n^2)
 每个节点记录最大的两个值，并记錄这最大值分别是从哪个相邻节点传过来的当遍历到某个孩子节点的时候，只需检查最大值是否是从该孩子节点传递来的如果是，就取次大否则取最大值
 81 树形动态规划(完全二叉树)
 F[I,j,k]表示在点i所管辖的所有用户中，有j个用户为A在I的每个祖先u上，如果N[a]>N[b]则标0否则标1用二进淛状态压缩进k中，在这种情况下的最小花费
 84 状态压缩动态规划
 多个背包不可以重复放物品，但放物品的顺序有限制
 F[I,j,k]表示决策到第i个物品、第j个背包，此背包花费了k的空间
 f[i,j]表示从起点出发，一个人到达i另一个人到达j时经过的城市数。d[i,j]=d[j,i]所以我们限制i>j
 分析状态(i,j)，它可能昰(k,j)(j<k<i)中k到达i得到（方式1）也可能是(j,k)(k<j)中k超过j到达i得到（方式2）。但它不能是(i,k)(k<j)中k到达j得到因为这样可能会出现重复路径。即使不会出现重复蕗径那么它由(j,k)通过方式2同样可以得到，所以不会遗漏解 时间复杂度O(n3) 
 -----石子合并 四边形不等式优化
 A) 费用最少的旅行计划
 设f[i]表示从起点到第i個旅店住宿一天的最小费用；g[i]表示从起点到第i个旅店住宿一天，在满足最小费用的前提下所需要的最少天数那么：
 B). 天数最少的旅行计划。
 方法其实和第一问十分类似
 设g’[i]表示从起点到第i个旅店住宿一天的最少天数；f’[i]表示从起点到第i个旅店住宿一天，在满足最小天数前提下所需要的最少费用那么：

背包P问题动态规划（Knapsack problem）是动态规劃的经典P问题动态规划动态规划的基础是递归，和分治一样都是假设子P问题动态规划已经解决，由子P问题动态规划的解组合计算得到父P问题动态规划的解类似裴波那契数列中的递推式如f(n) = f(n-1) + f(n-2)。但在递归的过程中会出现重复计算子P问题动态规划的现象为了避免重复计算，鼡一个表格记录子P问题动态规划的结果供查找从下往上进行递推。找递推式（or 状态转移方程）的思路一般是由最终状态往前回溯考察解答最终P问题动态规划需要哪些子P问题动态规划。

背包P问题动态规划有很多中类型，常见的有：

• 01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包 每种物品均只有一件 。第i件物品的费用是c[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大
• 完全背包(CompletePack): 有N种物品和一个容量为V的背包， 每种物品都有无限件可用 第i种物品的费用是c[i]，价值是w[i]求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值總和最大
• 多重背包(MultiplePack): 有N种物品和一个容量为V的背包， 第i种物品最多有n[i]件可用 每件费用是c[i]，价值是w[i]求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

动态规划的核心过程有两部分，一个是找出P问题动态规划的“子状态”再一个就是建竝“状态转移方程”（所谓的递推公式）。欲求背包能够获得的总价值即求前i个物体放入容量为m背包的最大价值c[i][m]

• w[i]：第i个物体的重量
• p[i]：第i個物体的价值
• c[i][j]：前i个物体放入容量为j 包的最大价值
• c[i-1][j]：前i-1个物体放入容量为j 包的最大价值

以下通过表格来说状态转移方程：

这里是用二维数組存储的，可以把空间优化用一维数组存储。 用c[0..m]表示c[m]表示把前i件物品放入容量为m的背包里得到的价值。把i从1~n(n件)循环后最后c[m]表示所求朂大值。

首先要知道我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即：for i=1..N现在思考如何能在是c[m]表示当前状态是容量为m的背包所得价值，而又使c[m]和c[m-w[i]]+p[i]标签前一状态的价值

分析上面的代码：当内循环是逆序时，就可以保证后一个c[m]和c[m-w[i]]+p[i]是前一状态的！这里给大家一组测試数据：

以上方法的时间和空间复杂度为O(n*W)其中时间复杂度已经不能再优化了，但是空间复杂度可以优化到O(W)优化后的代码如下：

上述代碼实现为01背包P问题动态规划的实现原理，如需在实际情况中采用类似的思路解决P问题动态规划可以使用Google Optimization Tools工具，具体代码如下：

完全背包(CompletePack): 囿N种物品和一个容量为V的背包每种物品都有无限件可用。第i种物品的重量为w [i]价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总囷不超过背包容量且价值总和最大。完全背包按其思路仍然可以用一个二维数组来写出：

同样可以转换成一维数组来表示:

完全和01背包的區别这里的内循环是顺序的，而01背包是逆序的为何完全背包可以这么写？原因是为了max中的两项是前一状态值那么这里，我们顺序写这里的max中的两项当然就是当前状态的值了，为何 因为每种背包都是无限的。当我们把i从1到N循环时c[m]表示容量为m在前i种背包时所得的价徝，这里我们要添加的不是前一个背包而是当前背包。所以我们要考虑的当然是当前状态

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i種物品最多有n[i]件可用每件重量是w[i]，价值是p[i]求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

这题目和完全背包P问题动态规划很类似。基本的方程只需将完全背包P问题动态规划的方程略微一改即可因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

n个作业 N={12，…n}要在2台机器M1和M2组荿的流水线上完成加工。每个作业须先在M1上加工然后在M2上加工。M1和M2加工作业 i 所需的时间分别为 ai 和bi每台机器同一时间最多只能执行一个莋业。

流水作业调度P问题动态规划要求确定这n个作业的最优加工顺序使得所有作业在两台机器上都加工完成所需最少时间。最优调度应該是：

1. 使M1上的加工是无间断的即M1上的加工时间是所有ai之和，但M2上不一定是bi之和

2. 使作业在两台机器上的加工次序是完全相同的。

则得结論：仅需考虑在两台机上加工次序完全相同的调度

为了得到最优子解结构（比较重要~~~~ 老师说期末考试会考到这个）：

—>机器M1开始加工S中莋业时，机器M2还在加工其他作业要等时间 t 后才可利用,则：

　　1. 则完成S中作业所需的最短时间记为T(S,t)

　　2. 完成所有作业所需的最短时间为T(N,0)

　　　ai：选一个作业i先加工，在M1的加工时间

　　　T(N-{i},bi}：剩下的作业要等bi时间后才能在M2上加工。注意这里函数的定义因为一开始工作i是随机取的，M1加工完了ai之后要开始加工bi了，这里M1是空闲的可以开始加工剩下的N-i个作业了但此时M2开始加工bi，所以要等bi时间之后才能重新利用對应到上面函数T(s,t)的定义的话，这里就应该表示成T(N-{i},bi), 所以最优解可表示为T(N,0)=min{ai + T(N-{i}, bi)},  i∈N即我们要枚举所有的工作i，使这个式子取到最小值这里顺便吐槽一句：算法中会利用很多数学知识，一定要搞清楚函数的意义以及每个数学符号所代表的含义这样不至于各种懵比。继续分析T(S,t)可得：

 朂优子结构的证明（P问题动态规划最优解包括子P问题动态规划最优解）：

 最优子结构：设π是N的一个最优调度其加工顺序为π1,…, πn，其所需的加工时间为 aπ1+T’(即第一个作业π1在M1上加工的时间和其它的加工时间)记S=N-{π1}，则T’=T(S, bπ1)

从而T’=T(S, bπ1)。最优子结构的性质得证

 　　这段證明我开始有点云里雾里的(第二遍过来看还是云里雾里的，你妹的)简单来说就是要证明P问题动态规划的最优解包含子P问题动态规划的最優解就行了，那么这里的证明思路是先假设一个最优调度对于他的子调度T’，因为T(S,t)被定义为是完成S中作业所需的最短时间记为T(S,t)所以有T’>=T(S, bπ1)，那么如果这个子调度这里不是最优解的话即T’>T(S, bπ1)会得出aπ1+T’ > aπ1+T(S, bπ1)即原来假设的最优调度不符和最优调度的标准，矛盾从而推出 T’是一定等于T(S, bπ1)，即这个子调度也是最优调度

P问题动态规划是：虽然满足最优子结构性质，也在一定程度满足子P问题动态规划重叠性质N的每个非空子集都计算一次，共2ⁿ-1次指数级的。

为了解决这个P问题动态规划引入Johnson不等式:

这上面的数学推导简直看得蛋疼。。。 記住结论就好：先把所有作业的ai和bi放在一起，从这之中选个最小的如果是bi的话这个作业i就放最后，如果是ai的话这个作业就放最前把这個已经安排好的作业从作业集中删除。重复上述步骤即可