【刷题日记】120. 三角形最小路径和

本次刷题日记的第 38 篇，力扣题为：120. 三角形最小路径和 ，中等

一、题目描述：

看到这个最小路径的题，我可能第一时间会先到使用回溯的方法，或者 动态规划的方式，当然方式很多，我们也可以找一些比较更加简单的方式来进行处理

二、这道题考察了什么思想？你的思路是什么？

一起来分析一下这题给出了我们那些重要的信息：

• 题目给出的是一个二维数组，排列起来正好是一个三角形，数组中都是整数，但是数据是没有规律的，我们要从顶向下计算一条路径，找到路径和最小的结果
• 此处从顶向下计算的路径还有严格按要求，下一层的选择中，需要是和上一层选择的数组索引相同，或者上上一层数字索引 + 1

根据这俩重要信息，按照正向的思维，我们不难相处可以通过这样的方式来进行模拟和推演

咱们从三角的第一层开始，按照规则，选取第一层的最小值，当然只有一个数，然后对第二层到其他层做处理，当然需要遵循  如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1

按照这个逻辑，我们可以看到上述的例子中，我们可以通过部分案例，例如上述的 第二个案例就是没有办法通过的

因为这种方式，我们并没有考虑到每一层的所有元素，就会导致可能漏掉某一些重要的数字

所以相应的就会写出这样的代码：

虽然编码也是按照上述思路来编写的，但是是没有办法跑过所有用例的

但是没有关系，我们肯定还有别的方式来很好的处理这种考虑不周全的情况

从上到下选取每一层的最小值，不太靠谱，那么我们是否可以从下到上，选择自己这一层，和上一层的最小和呢？

显然是可以的，我们可以这样来分析

用一个帮助数组来记录，从下到上遍历后的每一层计算出来的路径最小和

例如上述例子：

• 咱们三角的最后一行作为起始值，存放到帮助数组中
• 遍历倒数第 2 行的时候，我们用第二行的数字（若 索引为 i），与倒数第 1 行的（索引为 i   和 i+1）两个数字，分别计算，取最小值，然后将结果赋值到 帮助数组的 第 i 位上
• 每遍历一层，都会更新帮助数组，帮助数组中记录的永远是最小的路径和，且到三角的第一层的时候，那么计算结果就是帮助数组的第一个元素为整个链路的最小和

按照这种方式，下面这个例子做法也是一样的，解决起来也是 soso 滴明确

通过上述的方式，从下到上的计算路径最小和，思路清晰，方式简单，对于三角中的每一个数字都能考虑到位，剩下的就是来实现上述思路了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，此处编码需要注意咱们是从三角的最底层开始往上遍历和处理数据，注意可以直接将三角的最后一行赋一个初值给到我们的 helper 切片

func minimumTotal(triangle [][]int) int {
    // 先给
  helper := triangle[len(triangle)-1]
    // 计算每一行 i 和 i+1 得出的最小值
  for i:=len(triangle)-2;i>=0;i-- {
    for k,v:=range triangle[i] {
      helper[k] = min(v+helper[k],v+helper[k+1])
    }
  }
  return helper[0]
}
func min(a,b int) int {
  if a<b {
    return a
  }
  return b
}

通过上述编码，我们就可以看到写下来是非常轻松且明确的，按照思路，咱们从下往上来计算路径的最小和比较靠谱

四、总结：

对于空间复杂度很明显，我们引入了一个 hepler 切片，空间复杂度是 O(n) ，那么时间复杂度是多少呢？

我们可以看到此处咱们使用了 2 个循环，第一个循环的次数比较明确，是 triangle 的层数 - 1

但是 第二个循环确实一个动态的变化的，随着层数从下递增，第二个循环的次数越少，那么咱们的 时间复杂度是 O(n log m) 吗？

原题地址：120. 三角形最小路径和

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~