우리가 카드 게임을 한다고 가정해 봅시다. 우리는 각각에 번호가 있는 선형으로 배열된 여러 장의 카드를 받습니다. 카드의 숫자는 무작위로 배포됩니다. 그리고 카드의 시작과 끝에 숫자 1이 적힌 두 장의 카드가 삽입됩니다. 이제 게임에서 주어진 카드를 선택하여 최대 점수를 수집해야 합니다. 카드는 배열의 요소가 카드[i]의 수를 나타내는 배열 'cards'로 표시됩니다. 우리가 카드 i를 선택할 때, 우리는 포인트 카드[i - 1] * 카드[i] * 카드[i + 1]를 수집합니다. 카드를 집으면 카드[i - 1]와 카드[i]가 이웃이 됩니다. 따라서 이 주어진 카드에서 수집할 수 있는 최대 점수를 찾습니다.
따라서 입력이 카드 =[7, 5, 9, 10]과 같으면 출력은 1025
가 됩니다.따라서 게임에서 다음을 선택할 수 있습니다.
인덱스 1에 있는 카드는 7 * 5 * 9 =315포인트를 얻습니다.
새로운 인덱스 1에서 카드를 얻고 7 * 9 * 10 =630 포인트를 얻습니다.
인덱스 1에 있는 카드는 7 * 10 =70점을 얻습니다.
마지막 카드와 10포인트를 받으세요.
총점 =315 + 630 + 70 + 10 =1025
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- search() 함수를 정의합니다. x, y
- 온도 :=0
- x + 1 ~ y 범위의 z에 대해
- temp :=최대 (temp, search(x, z) + search(z, y) + cards[x] * cards[z] * 카드[y])
- 반환 온도
- 목록 카드의 시작과 끝에 각각 값 1과 1 삽입
- 반환 검색(0, 카드 크기 - 1)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(cards): def search(x, y): temp = 0 for z in range(x + 1, y): temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y]) return temp cards = [1] + cards + [1] return search(0, len(cards) - 1) print(solve([7, 5, 9, 10]))
입력
[7, 5, 9, 10]
출력
1025