动态规划本质上还是需要穷举，只是在穷举过程中，需要用 dp 数组记录已求得的结果，避免重复计算子问题，优化穷举过程。
穷举反应在状态转移方程的建立，穷举所有可能性和列出正确的状态转移方程是等价的，建立状态转移方程也就成为动态规划中的关键一环。
要正确的写出状态转移方程，需要：
- 明确状态
- 确定哪些参数影响状态
- 明确 dp 数组的参数含义
- 设置好所有 base case
千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。有时还可优化 dp 数组的空间复杂度。
计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。
dp 数组就是在追求“如何聪明地穷举”。
dp 数组遍历方向需要满足两点：
- 遍历的过程中，所需的状态必须是已经计算出来的。
- 遍历的终点必须是存储结果的那个位置。
其实 dp 数组的遍历方向，与暴力递归计算的方向正好相反。暴力递归是从存储结果的位置，递归到 base case，动态规划 dp 数组的遍历方向则是从 base case 到存储结构的位置。
二维 dp 数组的斜向遍历
以左上[0][0]与右下[m-1][n-1]连线分为左下部分和右上部分，每个部分又可以分为 左上->右下 遍历和 右下->左上 遍历。共四种遍历方式。
- 右上部分：左上->右下
for (int k = 2; k <= n; k++) {
for (int i = 0; i <= n - k; i++) {
int j = k + i - 1;
// 计算 dp[i][j]
}
}
- 右上部分：右下->左上
for (int k = 2; k <= n; k++) {
for (int i = n - k; i >= 0; i--) {
int j = k + i - 1;
// 计算 dp[i][j]
}
}
- 左下部分：左上->右下
for (int k = 2; k <= n; k++) {
for (int i = 0; i <= n - k; i++) {
int j = k + i - 1;
// 计算 dp[j][i]
}
}
- 左下部分：右下->左上
for (int k = 2; k <= n; k++) {
for (int i = n - k; i >= 0; i--) {
int j = k + i - 1;
// 计算 dp[j][i]
}
}
怎么考虑的呢，首先在整个循环过程中，外层循环不变，内层循环每次都变，所以在每次斜向遍历，都由内层循环控制方向。再记住外层循环 k 始终从 2 开始，到 n 为止。内层循环 i 的两个边界是 0 和 n-k。另一个坐标 j 始终为 j=k+i- 。
