LeetCode 120 - Triangle (Medium)

문제

LeetCode - 120번

풀이 과정

첫번째 행에서 마지막 행까지 도달하기 위한 거리의 최소 합을 구하는 문제입니다.

dp(row, idx) = row 행의 idx 열에서 마지막 행에 도달하기 위한 최소 거리 라고 정의한다면

다음과 같은 점화식을 얻을 수 있습니다.

dp[row][idx] = min(dp[row + 1][idx], dp[row + 1][idx + 1]) + triangle[row][idx]

코드

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
  const INF = 9999999;
  const rowLimit = triangle.length;
  const memo = Array.from(Array(rowLimit), () => Array(rowLimit + 1).fill(-1));

  function dp(row, index) {
    if (row.length >= index) {
      return INF;
    }

    if (row === rowLimit - 1) {
      return triangle[row][index];
    }

    if (memo[row][index] !== -1) {
      return memo[row][index];
    }

    memo[row][index] =
      Math.min(dp(row + 1, index), dp(row + 1, index + 1)) +
      triangle[row][index];

    return memo[row][index];
  }

  const answer = dp(0, 0);

  return answer;
};