120. 三角形最小路径和

问题描述

给定一个三角形 triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上（下标与上一层结点下标相同或等于上一层结点下标+1）。

示例：

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

算法思路

方法一：动态规划（二维DP数组）

1. 状态定义：
   dp[i][j] 表示从三角形顶部走到位置 (i, j) 的最小路径和。
2. 状态转移：
   • 首元素：dp[i][0] = dp[i-1][0] + triangle[i][0]
   • 尾元素：dp[i][i] = dp[i-1][i-1] + triangle[i][i]
   • 中间元素：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
3. 初始化：
   dp[0][0] = triangle[0][0]
4. 遍历顺序：
   从上到下，每行从左到右。
5. 结果：
   最后一行中的最小值。

方法二：动态规划（空间优化，一维数组）

1. 状态定义：
   dp[j] 表示从三角形底部走到当前行 j 列的最小路径和。
2. 状态转移：
   dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
3. 初始化：
   dp 数组初始化为三角形的最后一行。
4. 遍历顺序：
   从倒数第二行向上遍历，每行从左到右更新。
5. 结果：
   dp[0]（顶部元素值）。

代码实现

方法一：二维DP（自顶向下）

import java.util.*;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0); // 初始化起点

        for (int i = 1; i < n; i++) {
            // 每行首元素：只能从上一行首元素下来
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
            // 每行中间元素：取上一行相邻两个位置的最小值
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
            }
            // 每行尾元素：只能从上一行尾元素下来
            dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
        }

        // 在最后一行找最小值
        int res = dp[n-1][0];
        for (int i = 1; i < n; i++) {
            res = Math.min(res, dp[n-1][i]);
        }
        return res;
    }
}

方法二：一维DP（自底向上，空间优化）

import java.util.*;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        // 初始化：最后一行的值
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n-1).get(i);
        }

        // 从倒数第二行向上遍历
        for (int i = n - 2; i >= 0; i--) {
            // 更新当前行每个位置的最小路径和
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0]; // 顶部元素即为结果
    }
}

算法分析

• 时间复杂度：两种方法均为 O(n²)（n 为行数），需遍历每个元素。
• 空间复杂度：
  • 方法一：O(n²)（二维数组）。
  • 方法二：O(n)（一维数组）。

算法过程

方法二：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

1. 初始化 dp：
   dp = [4, 1, 8, 3]（最后一行）。
2. 处理倒数第二行（i=2）：
   • j=0：min(4,1) + 6 = 1 + 6 = 7 → dp[0]=7
   • j=1：min(1,8) + 5 = 1 + 5 = 6 → dp[1]=6
   • j=2：min(8,3) + 7 = 3 + 7 = 10 → dp[2]=10
   • 更新后：dp = [7, 6, 10, 3]
3. 处理第三行（i=1）：
   • j=0：min(7,6) + 3 = 6 + 3 = 9 → dp[0]=9
   • j=1：min(6,10) + 4 = 6 + 4 = 10 → dp[1]=10
   • 更新后：dp = [9, 10, 10, 3]
4. 处理第一行（i=0）：
   • j=0：min(9,10) + 2 = 9 + 2 = 11 → dp[0]=11
5. 返回结果：dp[0] = 11。

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：题目示例
    List<List<Integer>> triangle1 = new ArrayList<>();
    triangle1.add(Arrays.asList(2));
    triangle1.add(Arrays.asList(3, 4));
    triangle1.add(Arrays.asList(6, 5, 7));
    triangle1.add(Arrays.asList(4, 1, 8, 3));
    System.out.println("Test 1: " + solution.minimumTotal(triangle1)); // 11

    // 测试用例2：单行三角形
    List<List<Integer>> triangle2 = new ArrayList<>();
    triangle2.add(Arrays.asList(-10));
    System.out.println("Test 2: " + solution.minimumTotal(triangle2)); // -10

    // 测试用例3：两行三角形
    List<List<Integer>> triangle3 = new ArrayList<>();
    triangle3.add(Arrays.asList(1));
    triangle3.add(Arrays.asList(2, 3));
    System.out.println("Test 3: " + solution.minimumTotal(triangle3)); // 3（1+2）

    // 测试用例4：三行三角形
    List<List<Integer>> triangle4 = new ArrayList<>();
    triangle4.add(Arrays.asList(1));
    triangle4.add(Arrays.asList(2, 3));
    triangle4.add(Arrays.asList(4, 5, 6));
    System.out.println("Test 4: " + solution.minimumTotal(triangle4)); // 7（1+2+4）
}

关键点

1. 方法一边界处理：
   • 每行首尾元素只有一条路径。
   • 中间元素需比较上方两个相邻值。
2. 方法二空间优化：
   • 自底向上避免边界判断。
   • 从右向左更新避免覆盖（但此处从左向右更新不影响，因依赖 dp[j] 和 dp[j+1]）。
3. 遍历顺序：
   • 方法一：从上到下（需处理首尾边界）。
   • 方法二：从下到上（更简洁高效）。

常见问题

1. 为什么方法二选择自底向上？
   自底向上时，每个位置都有两个子节点，无需处理边界条件（如首尾元素），且能自然优化到一维空间。
2. 方法二中如何避免覆盖问题？
   更新 dp[j] 时，dp[j+1] 仍是下一行的值，且后续计算 dp[j+1] 时依赖的是 dp[j+1] 和 dp[j+2]，与已更新的 dp[j] 无关。
3. 方法一最后为何要遍历最后一行？
   最小路径可能出现在最后一行的任意位置，需比较所有值。