黑书上的原文：本节所有的内容都很重要，尤其是例题，决心掌握DP的读者应当话时间全部掌握。本节的难点是模型的理解，包括一些难度偏大的题目和动态规划理论中的一些问题。学习本节之后，应该对每道题目，都能在很短的时间内把思路完整的整理一遍。对于大部分题目，应当能很快的写出程序。
这里做几个约定：1、加上每道题的提交地址。2、每道题只写转移方程和思路，不贴代码，因为我以后还要再刷。3、个人愚见，大牛无视。
黑书上的经典例题。dp[i][j]表示i 到j添加的最小括号数。
dp[i][j] = Min {
dp[i+1][j-1] s[i]s[j] = “()” 或 s[i][j] = "[]" …………… 1
dp[i][k] + dp[k + 1][j] 把s分成si...sk, sk + 1...sj …………2
} dp[i][i] = 1;
这里对黑书上的写法做了一下简化，发现(S', [S', S'), S']这几种情况在Si...Sk, Sk + 1...Sj中已经包括了。
这题让输出匹配好的序列。。。所以纠结了。。。参考这里
思路是用pos[i][j]表示(i, j)段的拆分位置。初始是情况-1。当出现在dp[i][j] = dp[i][k] + dp[k+1][j]时，拆分位置是pos[i][j] = k。
根据pos[][] dfs输出括号序列。
难得一见的中文题。
均方差化简得 σ = ((1/n) ∑xi2) - (Δx)2 。在纸上写写，化简很简单，关键是能想到。。。已知Δx是定值，要保证σ 最小只需要保证xi2 最小就可以。s(x1, y1, x2, y2)表示(x1, y1) (x2, y2)所包含的区间所有值的和。dp(k, x1, y1, x2, y2)表示(x1, y1) (x2, y2)所包含的区间加k条割线割成k + 1块所得到的最小∑xi2值。当然，分横割和竖割两种情况。转移方程：
dp(k, x1, y1, x2, y2) = {
min(dp(k-1, x1, y1, i, y2) + s(i+1, y1, x2, y2)2, dp(k-1, i+1, y1, x2, y2) + s(x1, y1, i, y2)2); //横割
min(dp(k-1, x1, y1, x2, j) + s(x1, j+1, x2, y2)2, dp(k-1, x1, j+1, x2, y2) + s(x1, y1, x2, j)2); //竖割
}
然后记忆化搜索。。。
ps:第一次不知道是哪地方推错了还是怎么回事，样例直接不过，又敲了一遍过掉了。
1.5.1 例题3 决斗 Spoj 196. Musketeers
还可以在这里提交
O(n^3)的思想，把x点拆成x, x + n, dp[i][j] = 1表示i和j能相遇，要保证一个人能活下来就是保证i 和i + n 能相遇。初始化dp[i][i+1] = 1;
dp[i][j] = {
1 if(dp[i][k] && dp[k][j] && (mp[i%n][k%n] || mp[j%n][k%n]) 存在一个k使得i -> k，j -> k并且，i 能打败k，或者j 能打败k。
0 else
}
要注意的是必须遵循counterclockwise，所以要保证 j <= i + n， i + 1 <= k < j;
怀特先生是个大胖子，他很喜欢玩跳舞机（DDR），DDR的主要内容是用脚来踩踏板，踏板有四个方向的
箭头（如下图） 分别用1，2，3，4来代表。每首歌曲有一个箭头序列，游戏者必须按照这个序列一次用
某一只脚踩相应的踏板。在任何时候两只脚都不能在同一个踏板上但可以同时呆在中心位置
从中心移动到任何一个箭头耗费2单位体力，从任何一个箭头移动到相邻箭头耗费3单位体力，移动到相对的箭头耗费4单位体力，而留在原地再踩一下只需要1单位体力，两只脚不能同时在一个踏板上，但可以同时呆在中心板上。
总结：多阶段决策，理解无后效性的定义。这题需要注意的几点：case1、起始时双脚都在0位置；case2、1，2，3，4这几个位置不能直接踏两只脚。
首先要考虑怀特先生作出下一步决策是根据什么?这一点想到这道题就完成大半了。。。。神一般的dp啊，ym。
根据怀特先生当前双脚的位置进行转移， 设dp[x][y][k]表示应该跳第k个舞步时，左脚在x位置，右脚在y位置的最小体力耗费。移动的情况只能有如下几种：
a) 把一只脚从中心位置移动到目标位置
b) 移动到相邻位置
c)移动到相对位置
d)在原地踩一下
dp[x][y][k] = min(dp[x][a[k]][k+1] + sum(y, a[k]), dp[a[k][y][k] + sum(x, a[k])); //这样写已经考虑到case2了，想想为什么。^_^
sum(x, y)表示x到y消耗的体力。
最后记忆化搜索。。。
dp(i, a, b, k)表示第i堆，已经处理完a个，最上边一个是b，且b的顶面是k。判断合法的情况可以画个图看一下。
如图，写法有点搓。。。各种if。。。T_T
ps: 有一点值得注意的是，问题求的是m堆的和，也就是说我就算给他堆一堆，然后这个高度是最大的，那么这一堆就是解。（因为这一堆是可以拆的）开始时被这个纠结住了。。还到处问怎么保证分m堆，我好搓。。。。
题意：n个方格，每次可以消除相同颜色的所有相邻的方格，假设一次消除L个，则得分L^2，求最大得分。（可能出现消除中间的方格后两边的方格相连）
思路：先把方格预处理一下，col[i]表示第i整块连续方格的颜色，len[i]表示长度。dp(i, j, k)表示后边k块方格的颜色和col[j]相同时，合并(col[i], len[i]), (col[i+1], len[j+1]), (col[i+2], len[i+2])...(col[j], len[j] + k) (len[j]+k表示后边有k个并到len[j]上一起消除。)；
case1、k块方格的颜色跟len[j]正好相同，可以直接消除掉，dp(i, j, k) = dp(i, j - 1, 0) + (len[j] + k)^2;
case2、k快方格的颜色跟len[j]相同，并且和i...j之间某一整块p颜色相同则可以先消除dp(p + 1, j - 1, 0)， 再消除dp(i, p, len[j] + k)；这是一个递归的过程。
dp(i, j, k) = max(case1, case2);
在纸上画画，实现实现就清楚了。刚开始看的时候迷迷糊糊，总是不利解k表示的什么。。。T_T
因为case2中col[p] == col[j]，所以可以记录一下j前边出现与j颜色相同整块的位置pre[j]。这里也算是一个小优化。
青蛙的烦恼。。。我也烦恼了！仰慕黑书。。。有的地方其实可以写的更直观的，不明白为什么书上要那样些。。。
变换后的距离要比变换前短，所以得到一个结论：从1出发第一步只能到n或者2，从2出发只能到。同样的，如果第一步是2，从2出发第一步只能到n或则3。或者说要求区间[i, j]的最优值，开始从j 出发第一步只能是j - 1或者i，同样从i出发只能是i + 1或 j 。写道这里递归就很明显了。。。
dp(i, j, k) k = 0表示从i点出发，[i, j]中的点访问一次所得到的最小距离，k = 1表示从j 点出发，[i, j] 中的点访问一次所得到的最小距离。
k = 0 : dp(i, j, k) = MIN(dis(i, i + 1) + dp(i + 1, j, 0), dis(i, j) + dp(i + 1, j, 1));
k = 1 : dp(i, j, k) = MIN(dis(j, j - 1) + dp(i, j - 1, 1), dis(j, i) + dp(i, j - 1, 0));
ans = min(dp(0, n - 1, 0), dp(0, n - 1, 1));