• boj.kr/11602
• https://studykty.tistory.com/192 의 내용을 참고하여 품.
• https://github.com/ChoiWheatley/choi-workspace/blob/master/ALGORITHMS/bak/problem/11062/solution.hpp

TL;DR

DP[i][j] : i~j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수를 저장한다.

상대 플레이어도 같은 DP배열을 사용한다.

문제 특성상, 플레이어가 모든 카드를 반반 갈라먹기 때문에 (카드 개수가 홀수라면 근우가 하나 더 챙김) DP[i][j]에 대하여 cards[i:j].sum() - DP[i][j] 하면 턴 상관 없이 상대플레이어의 점수를 알 수 있다. 이 점을 착안하여 점화식을 세울 수 있다. 진짜 DP인지도 몰랐는데...

• 초기 조건
  DP[i, i] = c[i]
DP[i, i+1] = max(c[i], c[i+1])
• 점화식

DP[k, j] = max(c[k] + c[k+1 : j].sum() - DP[k+1, j],
               c[j] + c[k : j-1].sum() - DP[k, j-1])

• 점화식 의미
  카드의 리스트 중에서 맨 왼쪽 c[k] 또는 맨 오른쪽 c[j] 카드를 뽑고 상대 플레이어가 다음 범위에서 얻을 수 있는 최선의 점수를 해당 범위의 카드의 총합에서 뺀 결과를 서로 더한다면 이번 범위에서 얻을 수 있는 최선의 점수가 된다. 이거는 도대체 누구 머리에서 나온거냐