[LeetCode] 486. Predict the Winner

😎풀이

1. left 부터 right 까지의 최적 값을 저장할 2차원 DP 배열 생성
2. 좌측의 값을 뽑았을 때, 우측의 값을 뽑았을 때 최적의 점수를 사용
3. nums의 첫번째, 마지막 요소 중 Player 1이 승리할 수 있는 요소가 있는지 판별

function predictTheWinner(nums: number[]): boolean {
    const n = nums.length
    const dp = Array.from({ length: n }, () => Array(n).fill(null))
    function getMaxScore(left: number, right: number) {
        if(left === right) return nums[left]
        if(dp[left][right]) return dp[left][right]
        const pickLeft = nums[left] - getMaxScore(left + 1, right)
        const pickRight = nums[right] - getMaxScore(left, right - 1)
        dp[left][right] = Math.max(pickLeft, pickRight)
        return dp[left][right]
    }
    return getMaxScore(0, n - 1) >= 0
};