120.triangle

120. Triangle

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [[2], [3,4], [6,5,7], [4,1,8,3]]
2 3 6 1
2 3 5 1
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -104 <= triangle[i][j] <= 104

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Analyze

根据题意如果当前值的下标为 (m, n), 则其下一个数的下标为 (m + 1， n) 或者 (m + 1, n + 1)。

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  const cache = { smallest: Infinity }
  getSmaller(triangle, 0, 0, 0, cache)
  return cache.smallest
}

// m: witch row
// n: witch column
// result: current min value
var getSmaller = function(triangle, m, n, result, cache) {
  const sum = result + (triangle[m][n] ? triangle[m][n] : 0)
  if (m === triangle.length - 1) {
    cache.smallest = Math.min(cache.smallest, sum)
    return
  }

  getSmaller(triangle, m + 1, n, sum, cache)
  getSmaller(triangle, m + 1, n + 1, sum, cache)
}

此时提交的时候执行时间超时, 开始优化!

首先使用 f(m, n) = Math.min(f(m + 1, n), f(m + 1, n + 1)) + triangle[m][n] 优化、精简代码如下:

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  return getSmaller(triangle, 0, 0)
}

// m: witch row
// n: witch column
var getSmaller = function(triangle, m, n) {
  console.log('m', m, 'n', n, 'triangle', triangle[m][n])
  if (m === triangle.length - 1) {
    return triangle[m][n]
  }
  const a = getSmaller(triangle, m + 1, n)
  const b = getSmaller(triangle, m + 1, n + 1)
  return (a < b ? a : b) + triangle[m][n]
}

以 var triangle = [[2], [3,4], [6,5,7], [4,1,8,3]] 为例, 当前 getSmaller 函数执行次数为 15。调用栈如下:

2
3 4
6 5 7
4 1 8 3

m 0 n 0 triangle 2
m 1 n 0 triangle 3
m 2 n 0 triangle 6
m 3 n 0 triangle 4
m 3 n 1 triangle 1
m 2 n 1 triangle 5 <-
m 3 n 1 triangle 1 <-
m 3 n 2 triangle 8 <-
m 1 n 1 triangle 4
m 2 n 1 triangle 5 <-
m 3 n 1 triangle 1 <-
m 3 n 2 triangle 8 <-
m 2 n 2 triangle 7
m 3 n 2 triangle 8
m 3 n 3 triangle 3

此时可以发现箭头处的调用是相似的, 故而可以使用缓存减少调用栈的次数。缓存优化如下:

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  return getSmaller(triangle, 0, 0, {})
}

// m: witch row
// n: witch column
var getSmaller = function(triangle, m, n, cache) {
  console.log('m', m, 'n', n, 'triangle', triangle[m][n])
  if (m === triangle.length - 1) {
    return triangle[m][n]
  }
  const a = typeof cache[`${m + 1}_${n}`] === 'number'
    ? cache[`${m + 1}_${n}`]
    : getSmaller(triangle, m + 1, n, cache)
  const b = typeof cache[`${m + 1}_${n + 1}`] === 'number'
    ? cache[`${m + 1}_${n + 1}`]
    : getSmaller(triangle, m + 1, n + 1, cache)
  const result = (a < b ? a : b) + triangle[m][n]
  cache[`${m}_${n}`] = result
  return result
}

执行优化后式子, 调用栈如下, 可以发现此前箭头处重复的调用现已缩小为一次。

m 0 n 0 triangle 2
m 1 n 0 triangle 3
m 2 n 0 triangle 6
m 3 n 0 triangle 4
m 3 n 1 triangle 1
m 2 n 1 triangle 5 <-
m 3 n 1 triangle 1 <-
m 3 n 2 triangle 8 <-
m 1 n 1 triangle 4
m 2 n 2 triangle 7
m 3 n 2 triangle 8
m 3 n 3 triangle 3

接着使用动态规划的思路来解题, 因为其递归方向为至底向上, 因此可以减少缓存记忆化的环节。

思路为遍历 triangle 最后一行数据, 向上查找数据。取和为最小的那次数据。

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  let result = Infinity
  for (let n = 0; n < triangle[triangle.length - 1].length; n++) {
    const value = getSmaller(triangle, triangle.length - 1, n)
    result = Math.min(value, result)
  }
  return result
}

var getSmaller = function(triangle, m, n) {
  if (m === 0) {
    return triangle[m][n]
  }

  const a = getSmaller(triangle, m - 1, n)
  if (triangle[m - 1][n - 1] === undefined) {
    return a + triangle[m][n]
  }

  const b = getSmaller(triangle, m - 1, n - 1)
  return (a < b ? a : b) + triangle[m][n]
}

此时提交报超时, 如上解法已然是从下往上递归了呀, 难道这样子仍然没有满足动态规划思路么? 问题出在哪呢?

参考社区上同学的题解, 动态规划本质是从下往上的递归, 相比从上往下的递归, 它节省的是重复函数栈调用的开销。值得注意的是, 它也需要记忆化, 故而上述代码会超时, 下面给出记忆化的代码片段:

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  const arr = []
  for (let m = triangle.length - 1; m >= 0; m--) {
    for (let n = 0; n <= m; n++) {
      if (!arr[m]) arr[m] = []
      if (!arr[m + 1]) {
        arr[m][n] = triangle[m][n]
      } else {
        arr[m][n] = Math.min(arr[m + 1][n], arr[m + 1][n + 1]) + triangle[m][n]
      }
    }
  }
  return arr[0][0]
}

Similar Title

值得二刷