스톤 게임 II

1140. 스톤게임II

난이도:중

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

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

Alice와 Bob은 교대로 진행하며 Alice가 먼저 시작합니다. 처음에는 M = 1입니다.

각 플레이어의 차례에 해당 플레이어는 첫 번째 X개의 남은 더미에서 모든 돌을 가져갈 수 있습니다. 여기서 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. 동적 프로그래밍을 사용합니다. piles[i:]의 답에 대한 상태는 (i, m)이고 m이 주어진 경우입니다.

해결책:

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

1. 상태 및 전환 정의:

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

2. 기본 사례:

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

3. 재귀적 사례:

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

4. 전환 기능:

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

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

stoneGameII($piles1) . "\n"; // Output: 10
echo $solution->stoneGameII($piles2) . "\n"; // Output: 104
?>





  
  
  설명:




접두사 합계 계산: i부터 j까지의 돌 합계를 빠르게 계산하는 데 도움이 됩니다.

DP 배열 초기화: dp[i][m]는 앨리스가 m의 최대 선택 제한으로 더미 i에서 시작할 수 있는 최대 돌을 보유합니다.

동적 프로그래밍 전환: 각 더미와 m에 대해 앨리스가 취할 수 있는 가능한 더미 수를 반복하고 이에 따라 DP 배열을 업데이트하여 수집할 수 있는 최대 돌을 계산합니다.


이 접근 방식을 사용하면 중복 계산을 피하기 위해 동적 프로그래밍을 활용하여 해를 효율적으로 계산할 수 있습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

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


링크드인
깃허브



          

            
  

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