填表与刷表

填表法与刷表法

同一个 DP 转移，可以从两个方向来写：

填表法：固定当前状态，枚举它的来源，计算当前状态的值。
刷表法：固定当前状态，枚举它能到达的位置，用当前状态更新后续状态。

下面以数字三角形为例，对照这两种写法。

统一状态

给定一个数字均为正整数的三角形。从顶点出发，每次走向下一行的左下方或右下方，求到达最后一行的最大路径和。

例如：

      7
    3   8
  8   1   1

两种写法都定义 $dp[i][j]$ 为从顶点到达位置 $(i,j)$ 的最大路径和，包含当前位置的数字。

沿用前面的范围： $n\le500$ ， $1\le a[i][j]\le10^4$ 。使用全局数组：

const int N = 510;
int n, a[N][N], dp[N][N];

以下两段核心代码分别使用，均假定已经读入三角形，所有 $dp$ 初始为 $0$ ，并先设置 $dp[1][1]=a[1][1]$ 。

填表法：当前格子从哪里来？

固定位置 $(i,j)$ ，它的来源是上一行的 $(i-1,j-1)$ 和 $(i-1,j)$ 。选择较大的路径和，再加上 $a[i][j]$ ：

$$dp[i][j]=\max\bigl(dp[i-1][j-1],\ dp[i-1][j]\bigr)+a[i][j].$$

dp[1][1] = a[1][1];
for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
    }
}

由于数字均为正数，边界处不存在的来源用 $0$ 辅助即可，取最大值时会选中合法来源。

这段代码固定要填的格子，将所有来源比较完，再得到它的值。

刷表法：当前格子能走到哪里？

固定位置 $(i,j)$ ，可以走到下一行的 $(i+1,j)$ 和 $(i+1,j+1)$ ，分别更新：

$$dp[i+1][j]=\max\bigl(dp[i+1][j],\ dp[i][j]+a[i+1][j]\bigr),$$$$dp[i+1][j+1]=\max\bigl(dp[i+1][j+1],\ dp[i][j]+a[i+1][j+1]\bigr).$$

dp[1][1] = a[1][1];
for (int i = 1; i < n; ++i) {
    for (int j = 1; j <= i; ++j) {
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i + 1][j]);
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1][j + 1]);
    }
}

这段代码固定出发的格子，用它更新两个后续格子。 同一个后续格子可能被不同来源更新，因此必须与已有值取 max，不能直接覆盖。

对照示例

上面三角形的第二行状态为 $dp[2][1]=10$ 、 $dp[2][2]=15$ 。考虑第三行中间的格子，其数字为 $1$ 。

填表法：轮到 $(3,2)$ 时，一次比较两个来源：

dp[3][2]=\max(10,15)+1=16.

刷表法：两个来源先后更新它：

从 $(2,1)$ 出发，用 $10+1=11$ 更新，得到 $dp[3][2]=11$ 。
从 $(2,2)$ 出发，用 $15+1=16$ 更新，得到 $dp[3][2]=16$ 。

两种写法最终得到相同的状态：

       7
    10   15
  18   16   16

两者都按行从上到下处理。刷表法处理完第 $i$ 行后，第 $i+1$ 行收齐了所有来源的更新，才能继续向下转移。

答案与注意事项

两种写法的答案都是最后一行的最大值：

int ans = 0;
for (int j = 1; j <= n; ++j) ans = max(ans, dp[n][j]);
cout << ans << '\n';

填表法侧重枚举来源，刷表法侧重枚举去向；状态含义保持不变。
本题两种写法的时间复杂度均为 $O(n^2)$ ，空间复杂度均为 $O(n^2)$ ，改变转移方向不会自动降低复杂度。
无论哪种写法，都要按依赖顺序处理。本题从上一行转移到下一行，因此从上到下枚举行。
本题求最大值，更新时用 max；求最小值通常用 min；统计方案数通常用 +=，并保证方案不被重复统计。