LeetCode Triangle (JavaScript)

링크 : https://leetcode.com/problems/triangle/description/

문제 설명

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]]
Output: 11
Explanation: The triangle looks like:
23 4
 65 7
41 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

---

문제 풀이

1. dfs로 풀이 (시간 초과)

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  const dfs = (depth, index, sum, minimum) => {
    if (minimum < sum) return;
    if (depth === triangle.length - 1) {
      return Math.min(minimum, sum);
    }

    return Math.min(
      dfs(depth + 1, index, sum + triangle[depth + 1][index], minimum), 
      dfs(depth + 1, index + 1, sum + triangle[depth + 1][index + 1], minimum)
    );
  }
    
  return dfs(0, 0, triangle[0][0], Infinity);
};

 

2. dp (top-down) - 성공

최상단에서 다음 row에 대해 각 요소에서 가장 작은 값을 계산하며 마지막 row까지 계산하고, 최종적으로 마지막 row에 가장 작은 값을 리턴하면 됨

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

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

 

3. dp (bottom-up) - 성공

top-down 방식에서 불필요한 if-else 문을 지우고 더 최적화하여 bottom-up형태로 수정

/**
 * @param {number[][]} triangle
 * @return {number}
 */
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];
};

---

결론

dfs로는 depth가 깊어지면 시간 초과 오류가 발생.

dp를 이용해 top-down, bottom-up 형태로 문제를 해결할 수 있고 bottom-up 형태가 불필요한 if-else 문이 없어 더 빠른 시간안에 해결이 가능하다.