순진한 재귀 코인 문제를 변환할 때 메모리 오류

php 편집자 Yu Zai가 단순 재귀 코인 문제를 해결하는 동안 실수로 메모리 오류를 범했습니다. 이 문제는 일정량의 코인과 목표 금액이 주어지며, 목표 금액을 구성하는 다양한 조합을 모두 계산해야 합니다. 일반적으로 이 문제를 해결하기 위해 재귀를 사용할 수 있지만 메모리 오류로 인해 잘못된 계산이 발생했습니다. 이 글에서는 올바른 해결책을 다시 설명하고 비슷한 실수를 피하기 위한 몇 가지 실용적인 팁을 제공하겠습니다.

질문 내용

다음 문제를 해결하려고 합니다.

두 명의 플레이어가 동전 더미를 가지고 시작하며, 각 플레이어는 더미에서 동전 1~2개를 가져갈 수 있습니다. 마지막 동전을 가져간 플레이어가 패배합니다.

저는 다음과 같은 간단한 재귀 구현을 생각해 냈습니다. (놀이터):

으아악

위 코드는 정상적으로 작동합니다.

하지만 메모이제이션을 구현하여 이 솔루션을 개선하면(아래 또는 놀이터 참조) 잘못된 답을 얻게 됩니다.

으아악

두 번째 구현이 첫 번째 구현과 다른 값을 반환하는 이유에 대한 도움을 주시면 대단히 감사하겠습니다!

해결 방법

당신의 기억이 잘못되었습니다. 승자는 현재 동전 수뿐만 아니라 누구의 차례인지에 따라 달라집니다. 다음과 같은 것이 필요합니다:

으아악

위 내용은 순진한 재귀 코인 문제를 변환할 때 메모리 오류의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!