캔디라는 숫자 목록이 있고 두 사람이 가장 많은 캔디를 모으기 위해 경주하고 있다고 가정합니다. 여기에서 레이스는 턴 기반이고 사람 1이 먼저 시작하고 각 턴에서 앞이나 뒤에서 사탕을 줍습니다. 1이 다른 사람보다 사탕을 더 많이 모을 수 있는지 확인해야 합니다.
따라서 입력이 사탕 =[1, 4, 3, 8]과 같으면 사람 1이 첫 번째 라운드에서 사탕 8개를 가져갈 수 있고 두 번째 사람이 1 또는 3을 선택하는지 여부에 관계없이 사람 1이 출력되므로 출력은 True입니다. 남은 사탕을 가져가면 승리할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N :=사탕 크기
-
차이점() 함수를 정의합니다. 왼쪽, 오른쪽
-
왼쪽이 오른쪽과 같으면
-
캔디 반환[왼쪽]
-
-
(candies[left] − difference(left + 1, right))와 (candies[right] − difference(left, right − 1))
의 최대값을 반환합니다. -
주요 방법에서 다음을 수행하십시오 -
-
차이(0, N − 1)> 0이면 true를 반환하고, 그렇지 않으면 false
를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, candies): N = len(candies) def difference(left, right): nonlocal candies if left == right: return candies[left] return max(candies[left] − difference(left + 1, right), candies[right] − difference(left, right − 1)) return difference(0, N − 1) > 0 ob = Solution() candies = [1, 4, 3, 8] print(ob.solve(candies))
입력
[1, 4, 3, 8]
출력
True