Giả sử chúng ta đang chơi một trò chơi bài. Chúng tôi nhận được một số thẻ được sắp xếp tuyến tính với một số trên mỗi thẻ. Các số trên thẻ được phân phối ngẫu nhiên; và ở đầu và cuối của thẻ, hai thẻ được chèn với số 1 trên chúng. Bây giờ, trong trò chơi, chúng ta phải thu thập điểm tối đa bằng cách chọn các thẻ đã cho. Các thẻ được trình bày trong một 'thẻ' mảng trong đó các phần tử trong mảng đại diện cho số thẻ [i]. Khi chúng tôi nhận thẻ i, chúng tôi thu thập các thẻ tích điểm [i - 1] * thẻ [i] * thẻ [i + 1]. Khi chúng ta nhặt một thẻ, thẻ [i - 1] và thẻ [i] trở thành hàng xóm của nhau. Vì vậy, từ những thẻ nhất định này, chúng tôi tìm ra điểm tối đa mà chúng tôi có thể thu thập.
Vì vậy, nếu đầu vào giống như thẻ =[7, 5, 9, 10], thì đầu ra sẽ là 1025
Vì vậy, trong trò chơi, chúng ta có thể chọn -
Thẻ ở chỉ số 1 và nhận được 7 * 5 * 9 =315 điểm.
Thẻ ở chỉ số mới 1 và nhận được 7 * 9 * 10 =630 điểm.
Thẻ ở chỉ số 1 và nhận được 7 * 10 =70 điểm.
Thẻ cuối cùng và nhận được 10 điểm.
Tổng điểm =315 + 630 + 70 + 10 =1025
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm tìm kiếm (). Điều này sẽ lấy x, y
- tạm thời:=0
- đối với z trong phạm vi x + 1 đến y, thực hiện
- tạm thời:=tối đa (tạm thời, tìm kiếm (x, z) + tìm kiếm (z, y) + thẻ [x] * thẻ [z] * thẻ [y])
- nhiệt độ trở lại
- chèn các giá trị 1 và 1 tương ứng vào đầu và cuối thẻ danh sách
- trả về tìm kiếm (0, kích thước thẻ - 1)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]))
Đầu vào
[7, 5, 9, 10]
Đầu ra
1025