Triangle DP

120. Triangle

문제

주어진 triangle 삼각형의 상단에서 하단까지의 최소 경로 합계를 계산하는 문제이다.

테스트 케이스

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
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).

풀이

1. 행 triangle 에 해당하는 dp 배열을 생성하고 첫번째 행은 초기화한다.

    2

2. 열 triangle[i]의 처음과 끝은 그대로

• 열의 처음인 triangle[i][0]은 dp[i-1][0] + triangle[i][0] 값이고
• 열의 마지막인 dp[i][triangle[i].length-1]는 dp[i-1][triangle[i-1].length-1] + triangle[i][triangle[i].length-1]
• 조금 복잡해 보이지만 규칙일 뿐이고, 이전 행의 처음과 마지막 숫자를 더하는 것과 같다.

    2
   5 6     → 2+3, 2+4
11 ( ) 13  → 5+6, ( ), 6+7

3. 처음과 끝을 제외한 가운데 숫자들은 이전 행의 두 숫자 중 작은 숫자와 더해야 한다.

• dp[i][j]는 min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

    2
   5 6     → 2+3, 2+4
11 10 13   → 5+6, min(5,6)+5, 6+7

4. 마지막 행의 가장 작은 숫자를 반환한다.

코드

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
  const n = triangle.length
  const dp = new Array(n)
  dp[0] = triangle[0]

  for (let i = 1; i < n; i++) {
    dp[i] = new Array(triangle[i].length);
    dp[i][0] = dp[i-1][0] + triangle[i][0];
    dp[i][triangle[i].length-1] = dp[i-1][triangle[i-1].length-1] + triangle[i][triangle[i].length-1];
    
    for (let j = 1; j < triangle[i].length-1; j++) {
        dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
    }

  }

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