动态规划笔记

动态规划本质上还是需要穷举，只是在穷举过程中，需要用 dp 数组记录已求得的结果，避免重复计算子问题，优化穷举过程。

穷举反应在状态转移方程的建立，穷举所有可能性和列出正确的状态转移方程是等价的，建立状态转移方程也就成为动态规划中的关键一环。

要正确的写出状态转移方程，需要：

1. 明确状态
2. 确定哪些参数影响状态
3. 明确 dp 数组的参数含义
4. 设置好所有 base case

千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。优化方法无非是用备忘录或者 DP table，再无奥妙可言。有时还可优化 dp 数组的空间复杂度。

计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。
dp 数组就是在追求“如何聪明地穷举”。

dp 数组遍历方向需要满足两点：

• 遍历的过程中，所需的状态必须是已经计算出来的。
• 遍历的终点必须是存储结果的那个位置。
  其实 dp 数组的遍历方向，与暴力递归计算的方向正好相反。暴力递归是从存储结果的位置，递归到 base case，动态规划 dp 数组的遍历方向则是从 base case 到存储结构的位置。

二维 dp 数组的斜向遍历
以左上[0][0]与右下[m-1][n-1]连线分为左下部分和右上部分，每个部分又可以分为 左上->右下 遍历和 右下->左上 遍历。共四种遍历方式。

1. 右上部分：左上->右下

for (int k = 2; k <= n; k++) {
    for (int i = 0; i <= n - k; i++) {
        int j = k + i - 1;
        // 计算 dp[i][j]
    }
}

2. 右上部分：右下->左上

for (int k = 2; k <= n; k++) {
    for (int i = n - k; i >= 0; i--) {
        int j = k + i - 1;
        // 计算 dp[i][j]
    }
}

3. 左下部分：左上->右下

for (int k = 2; k <= n; k++) {
    for (int i = 0; i <= n - k; i++) {
        int j = k + i - 1;
        // 计算 dp[j][i]
    }
}

4. 左下部分：右下->左上

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- 。