文章来自 OI wiki ，转载仅作学习使用
动态规划应用于子问题重叠的情况：
给定一段钢条，和不同长度的价格，问如何切割使得总价格最大。
为了求解规模为 n 的原问题，我们先求解形式完全一样，但规模更小的子问题。
即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。
我们通过组合相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。
最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
动态规划的两种实现方法：
算导用子问题图上按照逆拓扑序求解问题，引出记忆化搜索。
重构解（输出方案）：转移的时候记录最优子结构的位置。
给出 n 个矩阵的序列，希望计算他们的乘积，问最少需要多少次乘法运算？
（认为 p×q 的矩阵与 q×r 的矩阵相乘代价是 p×q×r。）
完全括号化方案是指要给出谁先和谁乘。
两个要素：
具有最优子结构也可能是适合用贪心的方法求解。
注意要确保我们考察了最优解中用到的所有子问题。
要保持子问题空间尽量简单，只在必要时扩展。
最优子结构的不同体现在两个方面：
子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。
经典问题：
子问题空间要足够小，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。
存表记录最优分割的位置，就不用重新按照代价来重构。
子序列允许不连续。
每个 c[i][j] 只依赖于 c[i−1][j]、c[i][j−1] 和 c[i−1][j−1]。
记录最优方案的时候可以不需要额外建表（优化空间），因为重新选择一遍（转移过程）也是 O(1) 的。
给二叉搜索树的每个节点定义一个权值，问如何安排使得权值和深度的乘积最小。
考虑当一棵子树成为了一个节点的子树时，答案（期望搜索代价）有何变化？
由于每个节点的深度都增加了 1，这棵子树的期望搜索代价的增加值应为所有概率之和。
tD/eD 动态规划：
状态空间是 O(nt) 的，每一项依赖其他 O(ne) 项。
我们的目标是求出给定序列的一个最长的连续子序列，满足这个序列中的后一个元素 不小于 前一个元素。
因为是连续的，所以只要与上一个元素进行比较即可。
int a[MAXN];
int dp() {
int now = 1, ans = 1;
for (int i = 2; i <= n; i++) {
if (a[i] >= a[i - 1])
now++;
else
now = 1;
ans = max(now, ans);
}
return ans;
}
与最长连续不下降子序列不同的是，不需要这个子序列是连续的了。
求最长子序列的方法有两种。
O(n2) 的算法。每一次从头扫描找出最佳答案。
int a[MAXN], d[MAXN];
int dp() {
d[1] = 1;
int ans = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++)
if (a[j] <= a[i]) {
d[i] = max(d[i], d[j] + 1);
ans = max(ans, d[i]);
}
}
return ans;
}
O(nlogn) 的算法，参考了这篇文章 https://www.cnblogs.com/itlqs/p/5743114.html。
首先，定义 a1…an 为原始序列，d 为当前的不下降子序列，len 为子序列的长度，那么 dlen 就是长度为 len 的不下降子序列末尾元素。
初始化：d1=len1,len=1。
现在我们已知最长的不下降子序列长度为 1，那么我们让 i 从 2 到 n 循环，依次求出前 i 个元素的最长不下降子序列的长度，循环的时候我们只需要维护好 d 这个数组还有 len 就可以了。关键在于如何维护。
考虑进来一个元素 ai：
那么代码如下：
for (int i = 0; i < n; ++i) scanf("%d", a + i);
memset(dp, 0x1f, sizeof dp);
mx = dp[0];
for (int i = 0; i < n; ++i) {
*std::upper_bound(dp, dp + n, a[i]) = a[i];
}
ans = 0;
while (dp[ans] != mx) ++ans;
dp[i]=max(dp[j]+1),((j,i)∈E)
边界：dp[i][j]=1。
注意：dp[i][j] 表示的是闭区间。
也可以转化为 LCS 问题，只需要把 a 串反转当做 b，对 a 和 b 求 LCS 即可。
证明在 这里。
注意区分子串（要求连续）的问题。
O(n2)：dp[i]=max(dp[j]+1),s(j+1⋯i) 是回文
O(n)：Manacher
p[i] 表示从 i 向两侧延伸（当然要保证两侧对应位置相等）的最大长度。
为了处理方便，我们把原串每两个字符之间加一个（不包含在原串中的）#，开头加一个 $。
这样得到的回文串长度就保证是奇数了
考虑如果按顺序得到了 p[1⋯i−1]，如何计算 p[i] 的值？
如果之前有一个位置比如说是 id，有 p[id]+id>i 那么 i 这个位置是被覆盖了的，根据 id 处的对称性，我们找 p[id×2−i] 延伸的部分被 p[id] 延伸的部分所覆盖的那段，显然这段对称回去之后是可以从 i 处延伸出去的长度。
如果找不到呢？就先让 p[i]=1 吧。
之后再暴力延伸一下。
可以证明是 O(n) 的。
至于如何找是否有这么一个 id 呢？递推的时候存一个 max 就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define g(x, y, z) for (int x = (y), __ = (z); x <= __; ++x)
#define fd(x, y, z) for (int x = (y), __ = (z); x > __; --x)
#define gd(x, y, z) for (int x = (y), __ = (z); x >= __; --x)
const int MAXN = 120033;
char buf[MAXN];
char s[MAXN * 2];
int p[MAXN * 2];
int n, ans, T;
void init() {
int mx = 0, id;
f(i, 1, n) {
if (mx > i) p[i] = std::min(p[2 * id - i], p[id] + id - i);
else
p[i] = 1;
while (s[i + p[i]] == s[i - p[i]]) ++p[i];
if (p[i] + i > mx) {
mx = p[i] + i;
id = i;
}
}
}
int main() {
while (~scanf("%s", buf)) {
n = strlen(buf);
s[0] = '$';
s[1] = '#';
f(i, 0, n) {
s[i * 2 + 2] = buf[i];
s[i * 2 + 3] = '#';
}
n = n * 2 + 2;
s[n] = '\0';
init();
ans = 0;
f(i, 0, n) if (ans < p[i]) ans = p[i];
printf("%d\n", ans - 1);
}
return 0;
}
好像出成了某一年程设期末。
upd：其实是 程设期末推荐练习 里面的。
书上的提示是：从左到右扫描，对巡游路线的两个部分分别维护可能的最优解。
说的就是把回路给拆开吧。
dp[i][j] 表示 1⋯i 和 1⋯j 两条路径。
我们可以人为要求 1⋯i 是更快的那一条路径。
这样考虑第 j 个点分给谁。
如果是分给快的那条：
dp[i][j]=min(dp[i−1][j]+dis[i−1][j]), j=1⋯i
如果是慢的，原来是慢的那条就变成了快的，所以另一条是到 i−1 那个点：
dp[i][j]=min(dp[i−1][j]+dis[j][i]), j=1⋯i
答案是 min(dp[n][i]+dis[n][i])。
（从一开始编号，终点是 n）
代码：https://github.com/Ir1d/Fantasy/blob/master/openjudge/cssx/2018rec/11.cpp
把 dp[i][j] 定义反过来，不是 1⋯i 和 1⋯j。
改成是 i..n 和 j⋯n，不要求哪个更快。
这样的转移更好写：
我们记 k=max(i,j)+1
k 这个点肯定在两条路中的一个上，dp[i][j] 取两种情况的最小值即可。
dp[i][j]=min(dp[i][k]+dis[k][j],dp[k][j]+dis[i][k])
边界是：dp[i][n]=dp[n][i]=dis[n][i]。
答案是 dp[1][1]。
希望最小化所有行的额外空格数的立方之和。
注意到实际问题要求单词不能打乱顺序，所以就好做了起来。不要把题目看复杂。
dp[i]=min(dp[j]+cost[j][i])
不知道这样可不可做：有 n 个单词，可以不按顺序打印，问怎么安排，使得把他们打印成 m 行之后，每行的空格之和最小。
变换操作有 6 种，复制、替换、删除、插入、旋转、终止（结束转换过程）。
把空格符插入到字符串里，使得相似度最大。
定义了按字符比较的相似度。
然后发现最优对齐问题可以转换为编辑距离问题。
相当于仅有三个操作的带权编辑距离。
copy : 1 replace : -1 insert : -2
没有上司的舞会。
dp[x][0] 是没去，dp[x][1] 是去了。
dp[u][0]=max(dp[v][0],dp[v][1]),v∈son(u)
dp[u][1]=w[u]+dp[v][0],v∈son(u)
Viterbi algorithm 之前写词性标注的时候有用到，好像用在输入法里面也是类似的。
本题中用来实现语音识别，其实就是找一条对应的概率最大的路径。
ref：https://segmentfault.com/a/1190000008720143
玩过 opencv 的应该有印象，seam carving 就是在做 dp。
题中要求每一行删除一个像，每个像素都有代价，要求总代价最小。
限制：要求相邻两行中删除的像素必须位于同一列或相邻列。
dp[i][j]=min(dp[i−1][j],dp[i−1][j−1],dp[i−1][j+1])+cost[i][j]
边界：dp[1][i]=cost[1][i]。
相当于问怎么按顺序拼起来使得总代价最小。
等价于之前那个最优二叉搜索树。
dp[i][j]=min(dp[i][k]+dp[k][j])+l[j]−l[i]+1, k=i+1⋯j−1
注意 l[i] 表示的是第 i 个切分点的位置。
边界：dp[i][i]=0。
就按照区间 dp 的姿势来写就好了。
引理：存在最优投资策略，每年都将所有钱投入到单一投资中。
这是个很有趣的结论，dp 问题中很常见。
https://fogsail.github.io/2017/05/08/20170508/
剩下的就是个二维 dp，想成从 (1,i) 走到 (n,m) 的路径的问题，然后收益和代价就是边权，网格图只能往右下方走。
生产多了少了都有额外的成本，问怎么安排生产策略使得额外的成本尽可能地少。
cost[i][j] 表示剩下 i 个月，开始的时候有 j 台库存的最小成本。
https://walkccc.github.io/CLRS/Chap15/Problems/15-11/
v[i][j] 是考虑 i 之后的位置，总费用为 x 的最大收益。
https://walkccc.github.io/CLRS/Chap15/Problems/15-12/
类似于背包问题。
当选取的状态难以进行递推时（分解出的子问题和原问题形式不一样），考虑将问题状态分类细化，增加维度。