每日一题:三角形最小路径和

【题目指路】每日一题:三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 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

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

进阶：

• 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

刷题多的人可能一眼就看出来这是典型的线性DP入门问题。按照常规的学的DP推导就可以去做的。但是动态规划并没有那么容易去理解和学会(就素,我也不会,我是采购)。或者图论的知识也可以做这个题目，就直接把这个三角形建成一个有向图，然后使用最短路去求，也是可以做出来的。我这里给出的是我认为容易理解的方式来讲解这题的思路。

题目的意思很清晰明了，就是从顶点出发，求去到底部的最小路径和。按照正常的，暴力的思路，(我这里指的暴力是穷举的意思)，我们是不是可以从上到下去扫描累加，然后记录下来每条路径和，再通过比大小，就可以获得最终答案。使用示例1来举例说明

图所示：
   2
  3 4
 6 5 7
4 1 8 3

2 3 6 4 => 15
2 3 6 1 => 12
2 3 5 1 => 11
2 3 5 8 => 18
2 4 5 1 => 12
2 4 5 8 => 19
2 4 7 8 => 21
2 4 7 3 => 16

这是穷举的思路，那么怎么优化呢？其实就是去观察有什么需要重复计算或使用的。

从题目中如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。可以看出来这就是一个小三角的构成，而这整个三角形由一个个小三角组成。那么我们能知道小三角是怎么算，就可以类推。显然，一个小三角的最小值是顶点加上左右的小值。接下来我们要去算大三角的最小值。

怎么将这个大三角变成一个个小三角去算，或者说怎么把小三角消除生成一个最后的小三角，做完了这个操作后，就是答案了。

题目要求是从顶点出发到底部的最小值。自然地，我们就可以想到从上到下去看怎么操作。2出发，34选择一个，选3，接着只能选56，选5，接着选18，选1。好像这样确实就能得到答案。但是这对吗？有没有发现这个路径忽略了很多信息。假如图变成了这样呢？

图所示：
   2
  3 4
 6 5 1
4 1 8 1

按照前面的思路，路径还是锁死，得出来的还是2 3 5 1得到11，但实际上2 4 1 1得到8显然才是答案。

那么怎么解决这个问题？这个问题出在我们使用的信息很少，除了当前之外的信息都舍弃掉了，所以丢失了正确性。只要我们能够维护记录下消息，就可以解决。那么缺了什么信息？为什么会走235这个方向是因为根本没有241的记录，只要在确定走哪个方向的时候，有这些信息就可以了。也就是说，我们进到一个点的时候，确定什么方向时，需要知道每个方向剩下的路径有多长，选择剩下路径最短的走。从顶点开始，每一个选择下一个方向，都需要知道那个方向剩下的距离。

这是不是就是构成了一个递归？递归出口就是最底层。因为没有下一层了。剩下的距离要怎么记录？显然需要两个维度，起点和终点。

那么这要怎么实现？从顶点往下迭代或者递归向下搜索，每一层更新最小路径和。用二维数组记录到达 (i,j) 的最小路径和。

其实现在这个题目已经可以解了。但是题目还有信息。

只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题

现在我们是需要二维数组去记录信息，所以空间不符合。我们需要记录的信息为什么有二维，显然是因为需要确定起点和终点。但是，仔细思考一下，这个题目的起点不是确定的吗？这就说明完全可以省去一个维度。

前面已经思考过自顶向下需要知道剩下的路径长度才可以保持正确性，但是我们一转方向，自底向上去走呢？一旦有这个想法，这就很明朗了。终点是唯一确定的。从底部向上走，小三角的消除也可以一路往上消除。拿前面的图举例子

图所示：
   2
  3 4
 6 5 1
4 1 8 1

   2
  3 4
 7 6 2
 
   2
  9 6
  
   8

是不是很自然，很顺畅地消除了小三角，而且也不需要特别的信息，因为每一个消除的小三角的内容又构成下一个待消除的小三角，最终只留下终点的小三角。那就是答案。每次计算只依赖下一行的相邻两个元素。使用一维数组就可以存储剩下路径的最小路径和，计算完覆盖即可。

下面是代码的具体实现

public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        int n = triangle.Count;
        int[] dp = new int[n+1];
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[j] = Math.Min(dp[j],dp[j+1])+triangle[i][j];
            }
        }
        return dp[0];
    }
}

n 是三角形的高度。dp 用于记录每一行计算得到的最小路径和。n+1 是为了方便处理 dp[j+1]，最后多出一个位置不用。

外层循环 i：从底向上遍历每一行。内层循环 j：遍历当前行的每个元素。

dp[j] 和 dp[j+1] 代表下一行的两个相邻位置的最小路径和。加上当前行的 triangle[i][j] 就得到从当前点出发的最小路径和。

最终返回顶点的最小路径和。