LC120. 三角形最小路径和

题目描述

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

题目解析

题目在说什么

想象你站在一个数字金字塔的顶端，比如：

    2
   3 4
  6 5 7

你要从塔顶走到塔底，每次只能往下一层的相邻格子走。相邻的意思是：如果你在某一层的第 j 个位置，下一层你只能去第 j 个或第 j+1 个位置。每经过一个格子，就要加上那个格子里的数字。目标是找到一条路径，让经过的所有数字加起来最小。

比如上面的小金字塔，最小路径是 2→3→5，总和是 10。

思路是怎么来的

新手最容易想到的是：从顶开始，每次选下面两个数中较小的那个走。但这样会掉进“局部最优”的陷阱——比如上面例子，从 2 往下，3 和 4 里 3 更小，但 3 下面两个是 6 和 5，选 5 得到 2+3+5=10；如果一开始选 4，4 下面两个是 5 和 7，选 5 得到 2+4+5=11，反而更大。所以贪心不行。

那怎么才能找到全局最小的路径呢？一个聪明的办法是：从下往上想。

假设我们已经站在最后一层的某个格子上，那到这个格子的最小路径和就是它自己的数字（因为下面没路了）。再往上一层，某个格子的最小路径和，就等于它自己的数字加上它下面两个相邻格子中较小的那个最小路径和。这样一层层往上推，最后塔顶算出来的就是整个问题的最小路径和。

这个过程就像“搭积木”：先知道最下面一层每个格子的“成绩”（就是它们自己的数字），然后往上算每个格子的“成绩” = 自己的数字 + 下面两个“成绩”中较小的那个。这样一层层算到塔顶，答案就出来了。

代码逐步拆解

我们来看代码怎么实现这个“从下往上”的思路。

int n = triangle.size();  // 三角形的行数，比如上面例子 n=3
int[] dp = new int[n + 1];  // 创建一个长度为 n+1 的数组，用来存“成绩”

为什么数组长度是 n+1 而不是 n？因为后面计算时要用到 dp[j+1]，最后一行的 j+1 可能等于 n，多一个位置可以防止数组越界。初始时所有 dp 都是 0。

接下来是两层循环：

for (int i = n - 1; i >= 0; i--) {  // i 从最后一行（索引 n-1）往上到第 0 行
    for (int j = 0; j <= i; j++) {  // 对当前行的每个位置 j
        dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
    }
}

关键就在这一行：dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);

• triangle.get(i).get(j) 是当前格子自己的数字。
• dp[j] 和 dp[j+1] 是下一层（即第 i+1 层）第 j 和 j+1 个格子的“成绩”。注意：在更新 dp[j] 之前，dp[j] 里存的还是下一层的成绩，这正是我们需要的。
• Math.min(dp[j], dp[j+1]) 选两个下面格子中较小的成绩。
• 相加后存回 dp[j]，这样 dp[j] 就变成了当前层第 j 个格子的成绩。

用例子走一遍：

初始 dp = [0,0,0,0]

i=2（最后一行，数字 6,5,7）：
  j=0: dp[0] = 6 + min(0,0) = 6
  j=1: dp[1] = 5 + min(0,0) = 5
  j=2: dp[2] = 7 + min(0,0) = 7
  此时 dp = [6,5,7,0]

i=1（数字 3,4）：