[leetcode]1690. Stone Game VII

문제

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score's difference. Alice's goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

예시

Example 1:

- Input: stones = [5,3,1,4,2]
- Output: 6
- Explanation: 
	- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
	- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
	- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
	- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
	- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = []. 
    The score difference is 18 - 12 = 6.

Example 2:

- Input: stones = [7,90,5,1,100,10,10,2]
- Output: 122

제한사항

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

풀이1

Bobd의 목적은 score의 차이를 최소화 시키는 것, Alice의 목적은 score의 차를 최대화하는 것이다. 그런데 지금 현재의 것을 보는 것이 아니라, 앞으로의 것들도 확인을 해야한다.

dp에서는 점수차가 최대가 되는 값을 저장한다. dp[i]에 Math.max(total -S[i] - dp[j], total - S[j] - dp[j-1])을 계속 저장해 나간다.

var stoneGameVII = function(S) {
    let N = S.length, dp =Array(N).fill(0)
    for (let i = N - 2; ~i; i--) {
        
        let total = S[i]
        for (let j = i + 1; j < N; j++) {
            total += S[j]
            console.log(total,dp,total - S[i] - dp[j], total - S[j] - dp[j-1])
            dp[j] = Math.max(total - S[i] - dp[j], total - S[j] - dp[j-1])
            
        }
    }
    console.log(dp)
    return dp[N-1]
};

그 외

dp[i][j]를 먼저 이해하고, dp[i]로도 가능하다는 것을 이해하는데 많은 시간이 걸렸다.