Stones[i]가 왼쪽에서 i번째 돌의 값을 나타내는 배열이 있다고 가정합니다. 두 친구 Amal과 Bimal은 이 돌로 턴제 게임을 다시 하고 Amal은 항상 먼저 시작합니다. n개의 돌이 일렬로 배열되어 있습니다. 각 플레이어는 행에서 가장 왼쪽에 있는 돌이나 가장 오른쪽에 있는 돌을 제거하고 행에 있는 나머지 돌 값의 합과 동일한 점수를 얻을 수 있습니다. 누가 더 높은 점수를 얻을 것입니다 승리합니다. 이제 Bimal은 자신이 항상 이 게임에서 지는 것을 알았고 점수 차이를 최소화하기로 결정했습니다. Amal의 목표는 점수 차이를 최대화하는 것입니다. 따라서 Amal과 Bimal이 최적으로 플레이하는 경우 점수의 차이를 찾아야 합니다.
따라서 입력이 돌 =[6,4,2,5,3]과 같으면 Amal은 3을 취할 수 있으므로 출력은 6이 됩니다. 따라서 그의 점수는 6+4+2+5 =17, Bimal의 점수가 됩니다. 지금까지는 0이고 배열은 [6,4,2,5]와 같으며 Bimal은 6을 취하므로 그의 점수는 4+2+5 =11이고 이제 배열은 [4,2,5]입니다. 그런 다음 Amal은 4를 제거하므로 그의 점수 17+2+5 =24, 스톤 배열 [2,5] Bob은 2를 제거하므로 그의 점수 11+5 =16, 현재 스톤 배열 [5] 및 Amal은 값이 5인 마지막 돌을 제거합니다. 0점을 얻었으므로 최종 점수는 24 + 0 =24입니다. 따라서 점수의 차이는 24-16 =8입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=돌의 크기
- dp :=크기가 n이고 0으로 채워지는 배열
- n - 1에서 0 사이의 i에 대해 1 감소, do
- v :=돌[i]
- run_sum :=0
- i + 1 ~ n - 1 범위의 j에 대해
- new_run :=run_sum + 돌[j]
- dp[j] :=(new_run - dp[j]의 최대값) 및 (run_sum+v - dp[j - 1])
- run_sum :=new_run
- 반환 dp[n - 1]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(stones): n = len(stones) dp = [0] * n for i in range(n - 1, -1, -1): v = stones[i] run_sum = 0 for j in range(i + 1, n): new_run = run_sum+stones[j] dp[j] = max(new_run - dp[j], run_sum+v - dp[j - 1]) run_sum = new_run return dp[n - 1] stones = [6,4,2,5,3] print(solve(stones))
입력
[6,4,2,5,3]
출력
8