[LeetCode] 375. Guess Number Higher or Lower II

😎풀이

1. n보다 2 큰 2차원 행렬 생성
   1-1 WHY?, 1-indexed 인 n을 고려하며 핵심 점화식 Math.max(dp[start][i - 1], dp[i + 1][end]) 에서 초곽가 발생하지 않기 위함
2. 끝에서부터 역행하며 dp를 채움
   2-1. 내가 고를 수 있는 최악의 수 const curCost = i + Math.max(dp[start][i - 1], dp[i + 1][end])
   2-2. 중에서 최적의 선택 minCost = Math.min(minCost, curCost)
3. dp[1][n]을 통해 1부터 n까지의 수 중 반드시 승리할 수 있는 조건의 최솟값 확인

function getMoneyAmount(n: number): number {
    const dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0))
    for (let start = n - 1; start >= 1; start--) {
        for (let end = start + 1; end <= n; end++) {
            let minCost = Infinity
            for (let i = start; i <= end; i++) {
                const curCost = i + Math.max(dp[start][i - 1], dp[i + 1][end])
                minCost = Math.min(minCost, curCost)
            }
            dp[start][end] = minCost
        }
    }
    return dp[1][n]
}