โปรแกรมหาคะแนนสูงสุดที่เก็บได้ในเกมการ์ดใน Python

สมมติว่าเราเล่นเกมการ์ด มีการ์ดจัดเรียงเป็นแถว พร้อมตัวเลขบนแต่ละใบ ตัวเลขกระจายแบบสุ่ม และที่ปลายทั้งสองข้างมีการ์ดตัวเลข 1 เพิ่มเข้ามา ในเกม เราต้องเก็บคะแนนสูงสุดโดยการเลือกการ์ด การ์ดแสดงในอาร์เรย์ cards เมื่อเลือกการ์ด i จะได้คะแนน cards[i-1] * cards[i] * cards[i+1] เมื่อเลือกการ์ดแล้ว cards[i-1] และ cards[i+1] จะกลายเป็นเพื่อนบ้าน เราต้องหาคะแนนสูงสุดที่เก็บได้

เช่น ถ้าอินพุตคือ cards = [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

ขั้นตอนการแก้ปัญหา

1. กำหนดฟังก์ชัน search(x, y):
   • temp := 0
   • สำหรับ z ในช่วง x+1 ถึง y:
     • temp := max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
   • คืนค่า temp
2. แทรกค่า 1 และ 1 ที่ต้นและท้ายของรายการ cards
3. คืนค่า search(0, ขนาดของ cards - 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