题解 | #三角形取数(Hard Version)#

题目链接

题目描述

给定一个 $n$ 行的数字三角形，从顶点出发，每次可以向正下方、左下方或右下方移动，直到抵达最后一行。要求在整个过程中，向左下方移动的次数 $l$ 和向右下方移动的次数 $r$ 的差的绝对值不超过一个给定的整数 $d$ ，即 $|l - r| \le d$ 。目标是找到一条满足此条件的路径，使得路径上所有数值之和最大。

输入:

第一行两个整数 $n, d$ 。
接下来 $n$ 行，表示数字三角形。第 $i$ 行有 $2i-1$ 个整数。

输出:

一个整数，表示满足条件的最大路径和。

解题思路

本题是经典数字三角形问题的变种。直接从上往下并记录左右移动次数的解法，其复杂度为 $\mathcal{O}(n^3)$ ，对于某些语言（如Python）和稍大的 $n$ 来说可能会超时。

一个更高效的解法是采用从下往上的动态规划（Backward DP），可以将时间复杂度优化到 $\mathcal{O}(n^2)$ 。

定义状态: 我们定义 $dp[i][j]$ 为：从第 $i$ 行第 $j$ 列的格子出发，**走到最底层（第 $n-1$ 行）**所能获得的最大路径和。我们的最终目标是求 dp[0][0]。
状态转移方程: 我们从倒数第二行（ $i = n-2$ ）开始，向上遍历到第一行（ $i=0$ ）。对于第 $i$ 行的第 $j$ 个格子，从它出发能获得的最大和，等于它自身的值 values[i][j]，加上从它的三个子节点 (i+1, j), (i+1, j+1), (i+1, j+2) 出发所能获得的最大和中的最大值。状态转移方程为： $dp[i][j] = \text{values}[i][j] + \max(dp[i+1][j], dp[i+1][j+1], dp[i+1][j+2])$
边界条件与约束处理: 此算法的巧妙之处在于将 $|l-r| \le d$ 的约束在边界条件（即初始化第 $n-1$ 行的DP值）时就处理完毕。
- 从顶点 (0, 0) 出发到达第 $n-1$ 行，总共需要移动 $n-1$ 次。
- 设向左下方移动 $l$ 次，向右下方移动 $r$ 次。最终的列位置（以每行中心为0的偏移量）为 $k = r-l$ 。
- 题目约束为 $|r-l| \le d$ ，即 $|k| \le d$ 。
- 第 $n-1$ 行的列偏移量 $k$ 对应的数组索引为 $j = (n-1) + k$ 。
- 因此，终点列的索引 $j$ 必须满足 $|j - (n-1)| \le d$ ，即 $(n-1)-d \le j \le (n-1)+d$ 。
- 我们的边界条件是：
  - 对于第 $n-1$ 行，如果列索引 $j$ 在 [(n-1)-d, (n-1)+d] 范围内，则 dp[n-1][j] = values[n-1][j]。
  - 对于范围外的列 $j$ ，dp[n-1][j] 初始化为一个极小值（负无穷），表示从这些点出发的路径是不合法的。
最终结果: 通过从下往上的递推，任何通往非法终点（即第 $n-1$ 行上被设为负无穷的格子）的路径，其计算结果都会是负无穷，在 max 比较中被自动舍弃。最终，dp[0][0] 就是我们要求的最大路径和。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = -1e18; // 使用一个极小值表示不可达

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, d;
    cin >> n >> d;

    vector<vector<long long>> values(n);
    for (int i = 0; i < n; ++i) {
        values[i].resize(2 * i + 1);
        for (int j = 0; j < 2 * i + 1; ++j) {
            cin >> values[i][j];
        }
    }

    vector<vector<long long>> dp = values;

    // 初始化最后一行
    int center = n - 1;
    for (int j = 0; j < 2 * n - 1; ++j) {
        if (abs(j - center) > d) {
            dp[n - 1][j] = INF;
        }
    }

    // 从下往上递推
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= 2 * i; ++j) {
            long long max_next = max({dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j + 2]});
            if (max_next > INF + 1) { // 检查后继是否可达
                dp[i][j] += max_next;
            } else {
                dp[i][j] = INF;
            }
        }
    }

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

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    private static final long INF = -1_000_000_000_000_000_000L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();

        long[][] values = new long[n][];
        for (int i = 0; i < n; i++) {
            values[i] = new long[2 * i + 1];
            for (int j = 0; j < 2 * i + 1; j++) {
                values[i][j] = sc.nextLong();
            }
        }

        long[][] dp = new long[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new long[2 * i + 1];
        }

        // 初始化最后一行
        int center = n - 1;
        for (int j = 0; j < 2 * n - 1; j++) {
            if (Math.abs(j - center) <= d) {
                dp[n - 1][j] = values[n - 1][j];
            } else {
                dp[n - 1][j] = INF;
            }
        }

        // 从下往上递推
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= 2 * i; j++) {
                long maxNext = Math.max(dp[i + 1][j], Math.max(dp[i + 1][j + 1], dp[i + 1][j + 2]));
                if (maxNext > INF) {
                    dp[i][j] = values[i][j] + maxNext;
                } else {
                    dp[i][j] = INF;
                }
            }
        }

        System.out.println(dp[0][0]);
    }
}

import sys

def solve():
    # 读取输入
    n, d = map(int, input().split())
    values = []
    for _ in range(n):
        values.append(list(map(int, input().split())))

    # dp表初始化
    dp = [row[:] for row in values]
    INF = -float('inf')

    # 初始化最后一行，根据约束条件
    center = n - 1
    for j in range(2 * n - 1):
        if abs(j - center) > d:
            dp[n - 1][j] = INF

    # 从下往上进行动态规划
    for i in range(n - 2, -1, -1):
        for j in range(2 * i + 1):
            # 从三个子节点中选择最大路径和
            max_next = max(dp[i + 1][j], dp[i + 1][j + 1], dp[i + 1][j + 2])
            if max_next != INF:
                dp[i][j] = values[i][j] + max_next
            else:
                dp[i][j] = INF
    
    print(dp[0][0])

# 本题为单测试用例
solve()

算法及复杂度

算法：动态规划（从下往上）
时间复杂度： $\mathcal{O}(n^2)$ - 算法的主体是两层循环遍历数字三角形中的每个格子，其总数约为 $n^2$ 。
空间复杂度： $\mathcal{O}(n^2)$ - 主要用于存储DP表和输入的三角形数值。