[LeetCode] 174. Dungeon Game

😎풀이

1. 최소한의 체력 요구량을 미리 알아야 하므로 공주 위치에서 용사 위치로 이동
2. 각 이동의 계산 시 최소 1의 체력은 유지되어야 함
3. 용사 위치에 해당하는 값 반환

function calculateMinimumHP(dungeon: number[][]): number {
    // 핵심: 공주의 위치에서 시작 지점으로 추적
    const maxRow = dungeon.length - 1
    const maxCol = dungeon[0].length - 1
    const dp = Array.from({length: maxRow + 1}, () => Array(maxCol + 1).fill(0))
    for(let row = maxRow; row >= 0; row--) {
        for(let col = maxCol; col >= 0; col--) {
            const curDamage = dungeon[row][col]
            // 모든 계산은 최소 체력이 1이 될 수 있도록 계산(Math.max(1, ...))
            // 공주 방이 시작점
            if(row === maxRow && col === maxCol) {
                dp[row][col] = Math.max(1, 1 - curDamage)
                continue
            }
            // 끝 행인 경우(우측 이동만 추적)
            if(row === maxRow) {
                dp[row][col] = Math.max(1, dp[row][col + 1] - curDamage)
                continue
            }
            // 끝 열인 경우(하단 이동만 추적)
            if(col === maxCol) {
                dp[row][col] = Math.max(1, dp[row + 1][col] - curDamage)
                continue
            }
            // 아래 오른쪽 이동 중 합리적인 이동 선택(체력을 최소한으로 가져갈 수 있는)
            const minHP = Math.min(dp[row + 1][col], dp[row][col + 1])
            dp[row][col] = Math.max(1, minHP - curDamage)
        }
    }

    return dp[0][0]
};