Python에서 스톤 게임에서 최대 점수를 찾는 프로그램

<시간/>

여러 개의 돌이 연속적으로 배치되어 있고 이러한 각 돌에 배열 stoneValue에 지정된 관련 번호가 있다고 가정합니다. 각 라운드에서 Amal은 행을 두 부분으로 나눈 다음 Bimal은 이 부분의 모든 돌 값의 합인 각 부분의 값을 계산합니다. Bimal은 최대값을 가진 부분을 버리고 나머지 부분의 값만큼 Amal의 점수를 높인다. 두 부품의 값이 같을 때 Bimal은 Amal이 버릴 부품을 결정하도록 합니다. 다음 라운드는 나머지 부분으로 시작됩니다. 스톤이 하나만 남으면 게임이 종료됩니다. Amal이 얻을 수 있는 최대 점수를 찾아야 합니다.

따라서 입력이 stoneValue =[7,3,4,5,6,6]과 같으면 출력은

1라운드에서 Amal은 [7,3,4], [5,6,6]과 같이 행을 나눕니다. 왼쪽 행의 합은 14이고 오른쪽 행의 합은 17입니다. Bimal이 오른쪽 행을 버리고 Amal의 점수는 이제 14입니다.
2라운드에서 Amal은 행을 [7], [3,4]로 나눕니다. 따라서 Bimal은 왼쪽 행을 버리고 Amal의 점수는 (14 + 7) =21이 됩니다.
3라운드에서 Amal은 [3], [4] 행을 나눌 수 있는 단 하나의 선택권이 있습니다. Bimal이 오른쪽 행을 버리고 Amal의 점수는 이제 (21 + 3) =24입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dfs() 함수를 정의합니다. 시작, 끝
시작>=끝이면
- 0 반환
최대 점수 :=0
범위를 자르려면 시작부터 끝까지 수행하십시오.
- sum1 :=partial_sum[시작, 자르기]
- sum2 :=partial_sum[잘라내기+1, 끝]
- sum1> sum2 이면
  - 점수 :=sum2 + dfs(cut+1, end)
- 그렇지 않으면 sum1 일 때
  - 점수 :=sum1 + dfs(시작, 자르기)
- 그렇지 않으면
  - 점수 :=sum1 + dfs(start, cut) 및 dfs(cut+1, end)의 최대값
- max_score :=점수 및 max_score의 최대값
max_score 반환
getPartialSum() 함수를 정의합니다. 시간이 걸립니다
범위 0에서 n - 1에 있는 i에 대해 수행
- partial_sum[i, i] :=stoneValue[i]
범위 0에서 n - 1에 있는 i에 대해 수행
- i+1 ~ n - 1 범위의 j에 대해 수행
  - partial_sum[i, j] :=partial_sum[i, j-1] + stoneValue[j]
기본 방법에서 다음을 수행하십시오.
n :=stoneValue의 크기
partial_sum :=크기가 n x n이고 0으로 채워진 정사각형 배열
getPartialSum()
반환 dfs(0, n-1)

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(stoneValue):
   def dfs(start, end):
      if start >= end:
         return 0
      max_score = 0

      for cut in range(start, end):
         sum1 = partial_sum[start][cut]
         sum2 = partial_sum[cut+1][end]
         if sum1 > sum2:
            score = sum2+dfs(cut+1, end)
         elif sum1 < sum2:
            score = sum1+dfs(start, cut)
         else:
            score = sum1+max(dfs(start, cut), dfs(cut+1, end))
            max_score = max(score, max_score)
      return max_score


   def getPartialSum():
      for i in range(n):
         partial_sum[i][i] = stoneValue[i]
      for i in range(n):
         for j in range(i+1, n):
            partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j]


   n = len(stoneValue)
   partial_sum = [[0]*n for _ in range(n)]
   getPartialSum()
   return dfs(0, n-1)

stoneValue = [7,3,4,5,6,6]
print(solve(stoneValue))

입력

[7,3,4,5,6,6]