스톤 게임 II

1140. 스톤 게임 II

난이도:중간

주제:배열, 수학, 동적 프로그래밍, 접두사 합, 게임 이론

앨리스와 밥은 돌무더기를 가지고 게임을 계속합니다.일렬로 배열된더미가 있고, 각 더미에는 양의 정수 개수의 돌 더미[i]가 있습니다. 게임의 목표는 가장 많은 돌을 가지고 끝나는 것입니다.

앨리스와 밥은 교대로 진행하며 앨리스가 먼저 시작합니다. 처음에는 M = 1.

각 플레이어의 차례에 해당 플레이어는firstX개의 남은 더미에서모든 돌을 가져갈 수 있습니다. 여기서 1

돌을 모두 가져갈 때까지 게임은 계속됩니다.

앨리스와 밥이 최적으로 플레이한다고 가정하면앨리스가 얻을 수 있는 최대 돌 수.

를 반환합니다.

예 1:

• 입력:더미 = [2,7,9,4,4]
• 출력:10
• 설명:처음에 앨리스가 한 더미를 가져가면 밥은 두 더미를 가져가고, 앨리스는 다시 두 더미를 가져갑니다. 앨리스는 총 2 + 4 + 4 = 10개의 더미를 얻을 수 있습니다. 앨리스가 처음에 두 더미를 가져간다면 밥은 남은 세 더미를 모두 가져갈 수 있습니다. 이 경우 앨리스는 총 2 + 7 = 9개의 더미를 얻습니다. 따라서 더 크므로 10을 반환합니다.

예 2:

• 입력:더미 = [1,2,3,4,5,100]
• 출력:104

제약조건:

• 1 <= 더미.길이 <= 100
• 1 <= 더미[i] <= 10⁴

힌트:

1. 동적 프로그래밍 사용: 더미[i:]의 답에 대한 상태는 (i, m)이고 m이 주어집니다.

해결책:

두 플레이어가 모두 최적으로 플레이할 경우 앨리스가 얻을 수 있는 최대 돌 수를 찾으려면 동적 프로그래밍을 사용해야 합니다. 솔루션을 개발하기 위한 단계별 접근 방식은 다음과 같습니다.

1. 상태 및 전환 정의:

   • dp[i][m]가 최대 선택 한도 m인 더미 i에서 시작하여 앨리스가 수집할 수 있는 최대 돌을 나타내는 2D DP 배열을 정의합니다.
   • 접두사 합계 배열을 사용하면 하위 배열의 돌 합계를 효율적으로 계산할 수 있습니다.

2. 기본 사례:

   • 더 이상 선택할 돌이 없으면 점수는 0입니다.

3. 재귀적 사례:

   • 각 더미 i와 최대 허용 선택 m에 대해 가능한 모든 이동을 고려하여 앨리스가 수집할 수 있는 최대 돌을 계산합니다(1~2m 더미 사용).

4. 전환 기능:

   • 앨리스가 선택할 수 있는 각 더미 수에 대해 앨리스가 얻을 수 있는 총 돌 수를 계산하고 미래 상태의 결과를 사용하여 최적의 이동을 결정합니다.

이 솔루션을 PHP로 구현해 보겠습니다:1140. 스톤 게임 II

으아아아

설명:

1. 접두사 합계 계산:이는 i부터 j까지의 돌 합계를 빠르게 계산하는 데 도움이 됩니다.
2. DP 배열 초기화:dp[i][m]은 앨리스가 m의 최대 선택 제한으로 더미 i에서 시작할 수 있는 최대 돌을 보유합니다.
3. 동적 프로그래밍 전환:각 더미와 m에 대해 앨리스가 취할 수 있는 가능한 더미 수를 반복하고 이에 따라 DP 배열을 업데이트하여 수집할 수 있는 최대 돌을 계산합니다.

이 접근 방식을 사용하면 중복 계산을 피하기 위해 동적 프로그래밍을 활용하여 솔루션이 효율적으로 계산됩니다.

연락처 링크

이 시리즈가 도움이 되었다면repository에 별점을 주거나 좋아하는 소셜 네트워크에 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요:

• LinkedIn
• GitHub

위 내용은 스톤 게임 II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!