120. Triangle

题目

给定一个三角数组，返回从顶到低的最小路径值。

解析

image.png

对于一个三角形 t 来说，要求其顶到低的最短路径，我们将 t[0][0] 拿出来，此时三角形变成顶部两个元素3,4的梯形，可以将这个梯形看作以这两个元素为顶的三角形。此时，问题就变成了以 3,4 为顶的三角形哪个路径值最小。即
f(0,0) = min(f(1,0), f(1,1)) + t(0,0)
基于此递归，从底到顶，依次计算 f(m,n)。最终得到 f(0,0)。

1. 需要一个至少容纳 第 n 层元素的数组 f。，用于存储计算的路径值。
2. 自底向上运算，初始时，f 的值与最底层三角形相等。
3. 采用非递归，而是迭代的方式进行。一个指针 r 指向第 r 层。

伪代码

f = t[last]
for r = row-1; r<0; r--
  for i=0; i<len(t[r]); i++
    f[i] = min(f[i], f[i+1]) + t[r][i]
return f[0]

代码

func minimumTotal(triangle [][]int) int {
    t := triangle
    row := len(triangle)
    f := t[row-1]
    for r := row-2; r>=0; r-- {
        for i:=0; i < r+1; i++ {
            f[i] = min(f[i], f[i+1]) + t[r][i]
        }
    }
    return f[0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

image.png