LeetCode_486. Predict the Winner

 

leetcode.com/problems/predict-the-winner/

Predict the Winner - LeetCode

Solution1. 

 

2차원 배열을 이용하여 [start, end] 구간에서의 점수 차를 저장

즉, DP[start][end] >= 0 : win 을 의미하고 DP[start][end] < 0 : Lose 를 의미

 

if start == end :

    dp[start][end] = nums[start]

else :

    dp[start][end] = max( nums[start] - dp[start+1][end] , nums[end] - dp[start][end-1] )

 

위 식을 아래와 같이 loop를 돌면서 적용하면 완성

 

for length in range(N):   # length [0~N-1]

    for start in range(N-length):

        end = start + length

 

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        
        n = len(nums)
        dp = [[0]*n for _ in range(n)]
        
        for l in range(n):
            for s in range(n-l):
                e = s + l
                
                if s == e: 
                    dp[s][e] = nums[s]
                else:
                    dp[s][e] = max(nums[e]-dp[s][e-1], nums[s]-dp[s+1][e])
        
        return dp[0][-1] >= 0

 

 

Solution2. 

 

1차원 배열을 이용하는 방법, Solution1을 사용시 [1,5,233,7]을 적용하면 아래와 같이 dp 배열이 생성됨

 

[ [ 1, 4, 299 , 222 ],

  [ 0, 5, 288, -211],

  [ 0, 0, 233, 226],

  [ 0, 0, 0, 7 ] ]

 

좌측 아래 대각선에 사용되지 않는 공간이 생김으로 1차원 배열을 통해 이를 개선,

매 loop 마다 dp에는 length-1 기준으로 구해진 값이 저장되어 있음

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        
        n = len(nums)
        dp = nums[:]
        
        for l in range(1, n):
            new_dp = [0]*n 
            for s in range(n-l):
                e = s + l                
                # 현재 dp는 l-1의 결과
                new_dp[e] = max(nums[s]-dp[e], nums[e]-dp[e-1]) 
            dp = new_dp
                
        return dp[-1] >= 0