搜索不能用，贪心不敢用
判断技巧：
看问题的类型
看数据范围
\(2\).基本步骤
设计状态
确定初始状态
推导状态转移方程
\((1)\). 设计状态（阶段）
主要思想：问什么，设什么；从数据范围里猜测状态
思路：
满状态求出的最优解就是答案——最优解问题
状态即为答案，该状态是否能够达到即为该答案是否合法——可行解问题
\((2)\). 确定初始状态
常见\(DP\)初始状态的确定：
线性\(DP\)：左端点、右端点、边界外
区间\(DP\)：长度为 \(0/1/2\) ……
背包\(DP\)：背包大小为 \(0\)
树形\(DP\)：叶子节点、根节点
状压\(DP\)：\(0\) 状态或题目给定的起始状态
\((3)\). 推导状态转移方程
主要思想：小问题 -> 大问题
分情况讨论：考虑最后一步的决策。
常见\(DP\)归类：
线性\(DP\)：左 -> 右；右 -> 左
区间\(DP\)：短 -> 长
背包\(DP\)：小 -> 大
树形\(DP\)：上 -> 下；下 -> 上
状压\(DP\)： \(0\) 状态 -> 满状态；起始状态 -> 目标状态
其余：记忆化搜索
\(3\).典型题型
\((1)\).线性\(DP\)
\(Problem\ 1\)：最长不下降子序列
状态的表示： \(f[i]\) 表示以 \(i\) 为结尾的最长不下降子序列的长度。
状态转移方程：\(dp[i]=max(dp[i],dp[j]+1);\ (a[j]<a[i])\ (0<=j<i)\)
时间复杂度：\(O(n^2)\)
\(Problem\ 2\): [\(NOIP\)提高组][\(2013\)] 花匠
原题传送门
\(Problem\ 3\)：[\(NOIP\)普及组][\(2018\)] 摆渡车
原题传送门
\(Problem\ 4\)：[\(NOIP\)提高组][\(2014\)] 飞扬的小鸟
原题传送门
\((2)\).区间\(DP\)
主要问题：求某区间的最优解
阶段：总区间
子问题：某段区间
\(Problem\ 1\)：石子归并
状态的表示：\(f[i][j]\) 表示合并自 \(i\) 到 \(j\) 堆的代价
\(Problem\ 2\)：凸多边形三角划分
给定一个具有N（N＜50）个顶点的凸多边形以及每个顶点的权值。问如何把这个凸多边形划分成N-2个互不相交的三角形，从而使得这些三角形顶点的权值的乘积之和最小？
状态的表示：\(f[i][j]\) 表示从第 \(i\) 到 \(j\) 个点进行三角划分后的最小乘积和。
状态的转移：\(f[i][j] = min\{f[i][k]+f[k][j]+v[i]*v[j]*v[k]\}\) //v[i]指i的权值
\((3)\).背包\(DP\)（分配类\(DP\)）
基本类型：
\(01\) 背包（link）
完全背包（link）
多重背包（待更）
\(Problem\ 1\)：[\(NOIP\)提高组][\(2015\)] 子串
原题传送门
\(Problem\ 2\)：[\(NOIP\)普及组][\(2005\)] 采药
原题传送门
\(Problem\ 3\)：[\(NOIP\)提高组][\(2018\)] 货币系统
原题传送门
\(Problem\ 4\)：[\(NOIP\)普及组][\(2019\)] 纪念品
原题传送门
\(Problem\ 5\)：机器分配
原题传送门