Chương trình tìm điểm tối đa có thể thu được trong trò chơi bài Python

Cho mảng cards biểu diễn các lá bài xếp tuyến tính, mỗi lá có một số. Thêm hai lá bài giá trị 1 vào đầu và cuối. Khi chọn lá bài ở vị trí i, thu được điểm cards[i-1] * cards[i] * cards[i+1]. Sau khi chọn, cards[i-1] và cards[i+1] trở thành hàng xóm. Tìm tổng điểm tối đa có thể thu được.

Ví dụ: cards = [7, 5, 9, 10] → kết quả 1025.

Giải thuật (Quy hoạch động)

1. Thêm giá trị 1 vào đầu và cuối mảng
2. Định nghĩa hàm search(x, y) trả về điểm tối đa từ đoạn (x, y)
3. Thử mọi vị trí z giữa x và y làm lá bài chọn cuối cùng trong đoạn
4. Công thức: search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y]
5. Lấy giá trị lớn nhất

Ví dụ triển khai

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