数字三角形模型

前言：

数字三角形模型（Digital Triangle Model）是动态规划（DP）中一个非常经典的模型，主要用于解决“路径最优值”类型的问题。是指在一个从上到下的三角形结构中，从顶端出发，每一步只能走到下一层相邻的两个位置中的一个，目标是找到一条路径，使得路径上的数字和最大或最小。

1. E – Hungry Takahashi

题目链接：

https://atcoder.jp/contests/abc415/tasks/abc415_e

思路：

我们使用逆向动态规划，从终点开始反推到起点。

定义状态：

dp[i][j] 表示：如果高桥在第 i + j + 1 天结束后正好位于格子 (i, j)，那么为了确保后续所有天数都不会饿死，他此时手中最少需要持有的金币数。

之所以是第 i + j + 1 天，是因为从 (0, 0) 开始，每次只能向右或向下走一格，到达 (i, j) 恰好需要走 i + j 步，所以是第 i + j + 1 天。

状态转移：

每个状态 dp[i][j] 可以更新它的上方格子 (i – 1, j) 和左方格子 (i, j – 1)。

以 (i, j) 向上转移为例：

从 (i – 1, j) 移动到 (i, j)，发生在第 i + j 天（数组下标为 i + j − 1）；
在 (i – 1, j)，高桥会先收集 A[i – 1][j] 个金币；
然后他要消费 P[i + j − 1] 个金币吃饭；
接着进入 (i, j)，而 dp[i][j] 表示他进入该格子前必须手上至少有这么多金币。

定义 X 为在到达(i – 1, j)之前获得的金币，因此，他在进入 (i – 1, j) 时，手上需要携带的金币满足：

\(X + G[i-1][j] – P[i+j-1] ≥ dp[i][j]\)

也就是说：

\(X ≥ dp[i][j] – G[i-1][j] + P[i+j-1]\)

因为金币数量不能为负，最少需要的 X 是：

\(max(0, dp[i][j] – G[i-1][j] + P[i+j-1])\)

所以：

\(dp[i-1][j] = min(dp[i-1][j], max(0, dp[i][j] – G[i-1][j] + P[i+j-1]))\)

同理可得，从 (i, j) 向左方 (i, j – 1) 转移的公式为：

\(dp[i][j-1] = min(dp[i][j-1], max(0, dp[i][j] – G[i][j-1] + P[i+j-1]))\)

由于 (i – 1, j) 或 (i, j – 1) 可能也会被其他格子更新过，所以我们要在原有 dp 值基础上取 min，保持最优。

终点初始化:

终点为 (H – 1, W – 1)，到达这一天是第 H + W − 1 天（对应数组下标 H + W − 2）。

他当天收集 A[H – 1][W – 1] 个金币，然后需要花费 P[H + W − 2] 个金币买食物。

如果收集的金币不足，那差额就必须提前携带。因此：

\(dp[H-1][W-1] = max(0, P[H+W-2] – G[H-1][W-1])\)

最终答案：

完成逆向 DP 后，dp[0][0] 就是我们要求的答案——从起点出发，为了走完整个过程所需的最小初始金币数。

关键代码：

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<vector<ll>> g(n + 10, vector<ll>(m + 10));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> g[i][j];

    vector<int> p(n + m + 10);
    for (int i = 0; i < n + m - 1; ++i)
        cin >> p[i];

    vector<vector<ll>> dp(n + 10, vector<ll>(m + 10, 1e18));
    dp[n - 1][m - 1] = max(0ll, p[n + m - 2] - g[n - 1][m - 1]);
    for (int i = n - 1; ~i; --i)
    {
        for (int j = m - 1; ~j; --j)
        {
            if (i)
                dp[i - 1][j] = min(dp[i - 1][j],
                                   max(0ll, p[i + j - 1] + dp[i][j] - g[i - 1][j]));
            if (j)
                dp[i][j - 1] = min(dp[i][j - 1],
                                   max(0ll, p[i + j - 1] + dp[i][j] - g[i][j - 1]));
        }
    }

    cout << dp[0][0] << endl;
}

前言：