Java动态规划解决数字三角形最大路径和问题

落日邮差

发布时间：2026-10-16| 5人浏览过

原创

在处理数字三角形最大路径和这类经典算法问题时，直接自上而下搜索会导致大量重复计算。利用动态规划思想，采用自底向上的策略可以高效求出最优解。本文将详细讲解Java语言下的具体实现步骤与代码逻辑。

问题分析与解题思路

给定一个数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。例如以下示例：

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

若采用记忆化搜索或普通递归，时间复杂度较高。更优的策略是逆向思维：从最后一层开始向上计算。对于第 i 行第 j 列的数字，它只能走到下一行的 (i+1, j) 或 (i+1, j+1)。如果我们已知下一行各个位置能到达的最大路径和，那么当前位置的最大路径和就是：当前值 + max(左下子节点最大值, 右下子节点最大值)。

这种“滚雪球”式的累加过程，可以将空间复杂度优化为原地修改（或在同一数组中进行），且逻辑清晰直观。

第1步：定义数据输入格式

首先明确输入规范，以便构建相应的数据结构：

输入行数：第一行包含整数 n，表示数字三角形的层数（1 ≤ n ≤ 500）。
三角形数据：接下来 n 行，每行包含若干整数。第 i 行（从0开始计数或1开始均可，代码中通常用0索引）包含 i+1 个整数。
数值范围：三角形中的整数在 [-10000, 10000] 之间。

第2步：初始化二维数组并读取数据

使用 int[n][] 的锯齿状数组存储三角形。Java中不规则二维数组的创建方式如下：

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[n][];
for(int i = 0; i < n; i++){
    // 第 i 行有 i+1 个元素
    nums[i] = new int[i+1];
    for(int j = 0; j < i+1; j++){
        nums[i][j] = sc.nextInt();
    }
}

此时，nums[0][0] 是顶点，nums[n-1] 是底层数组。

第3步：自底向上执行动态规划状态转移

这是算法的核心部分。我们需要从倒数第二行（索引 n-2）开始，一直向上处理到第一行（索引 0）。对于每一行的每个元素，更新其值为自身加上左右两个子节点中的较大者。

for(int i = n - 1; i > 0; i--){
    // 遍历当前行的所有元素
    for(int j = 0; j < nums[i].length - 1; j++){
        // 状态转移方程：父节点 += max(左子节点, 右子节点)
        nums[i-1][j] += Math.max(nums[i][j], nums[i][j+1]);
    }
}

执行过程图解：

假设我们处理到倒数第二层，该行节点会分别取下方两个节点的最大值进行累加。随着循环向上推进，每一层的数值都代表了从该点出发到达底层的最大路径和。

当循环结束，nums[0][0] 中存储的值即为整个三角形的最大路径和。

第4步：输出结果

直接打印 nums[0][0] 即可。

System.out.println(nums[0][0]);

完整Java代码示例

将上述步骤整合，完整的可运行代码如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if(!sc.hasNextInt()) return;
        
        int n = sc.nextInt();
        int[][] nums = new int[n][];
        
        // 1. 读取三角形数据
        for(int i = 0; i < n; i++){
            nums[i] = new int[i+1];
            for(int j = 0; j < i+1; j++){
                nums[i][j] = sc.nextInt();
            }
        }
        
        // 2. 自底向上动态规划
        // 从最后一行的上一行开始往上推
        for(int i = n - 1; i > 0; i--){
            for(int j = 0; j < nums[i].length - 1; j++){
                // 关键操作：将较大子节点的值累加到父节点
                nums[i-1][j] += Math.max(nums[i][j], nums[i][j+1]);
            }
        }
        
        // 3. 输出顶层最大值
        System.out.println(nums[0][0]);
    }
}

验证示例

输入样例：

逻辑推演：

原底层为 4 5 2 6 5。
上一层 2 7 4 4 变为：
2+max(4,5)=7, 7+max(5,2)=12, 4+max(2,6)=10, 4+max(6,5)=10 → 新行为 7 12 10 10
继续向上类推，最终顶层 7 会加上下方计算出的最大路径值。