[LeetCode] 120. Triangle

😎풀이

dp를 사용하여 메모이제이션 하며 최소한의 공간으로 풀이가 가능한 문제이다.

top down 방식으로 풀이하였지만, 위에서 아래로 내려가는 경우는 dfs를 사용하여 복잡하고 공간 복잡도가 늘어날 수 밖에 없는 구조라는 점을 확인했음

최종적으로 bottom up 방식으로 풀이하였음

function minimumTotal(triangle: number[][]): number {
    // 삼각형의 마지막 행의 길이만큼의 DP 배열을 생성
    const dp: number[] = [...triangle.at(-1)];
    
    // 아래에서부터 위로 올라가면서 각 위치까지의 최소 경로 합을 계산
    for (let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            // 현재 위치(i,j)에서 아래 행으로 이동할 때
            // 왼쪽 아래(j)와 오른쪽 아래(j+1) 중 더 작은 값을 선택하고
            // 현재 위치의 값을 더함
            dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
        }
    }
    
    // dp[0]에는 최상단에서부터의 최소 경로 합이 저장됨
    return dp[0];
}