120. Triangle

原题：120. Triangle

思路

DP。走到第i层第j个节点的最小路径和为dp[i][j] = min( dp[i-1][j-1], dp[i-1][j] )。

source code

// Runtime: 60 ms, faster than 57.29% of JavaScript online submissions for Triangle.
// Memory Usage: 37.4 MB, less than 100.00% of JavaScript online submissions for Triangle.
var minimumTotal = function (triangle) {
  if (!triangle || !triangle.length) {
    return 0;
  }
  const dp = new Array(triangle.length).fill(1).map((v) => []);
  for (let i = 0; i < triangle.length; i++) {
    for (let j = 0; j < triangle[i].length; j++) {
      if (i > 0) {
        const a = dp[i - 1][j - 1];
        const b = dp[i - 1][j];
        dp[i][j] =
          triangle[i][j] +
          Math.min(a === void 0 ? Infinity : a, b === void 0 ? Infinity : b);
      } else {
        dp[i][j] = triangle[i][j];
      }
    }
  }

  return Math.min(...dp[dp.length - 1]);
};

test cases

test("test1", () => {
  const triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]];
  expect(minimumTotal(triangle)).toEqual(11);
});

test("test2", () => {
  const triangle = [];
  expect(minimumTotal(triangle)).toEqual(0);
});

test("test3", () => {
  const triangle = [[1]];
  expect(minimumTotal(triangle)).toEqual(1);
});

test("test4", () => {
  const triangle = [[1], [-5, -2], [3, 6, 1], [-1, 2, 4, -3]];
  expect(minimumTotal(triangle)).toEqual(-3);
});

更简洁的写法

// discuss中发现的更简洁写法，巧妙地避免了边界的判断
var minimumTotal = function (triangle) {
  for (let i = triangle.length - 2; i >= 0; i--)
    for (let j = 0; j < triangle[i].length; j++)
      triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
  return triangle[0][0];
};