สมมุติว่าเรากำลังเล่นเกมไพ่ เราได้รับไพ่หลายใบเรียงเป็นเส้นตรงพร้อมตัวเลขบนแต่ละใบ ตัวเลขบนการ์ดจะถูกสุ่มแจก และที่จุดเริ่มต้นและจุดสิ้นสุดของไพ่ ไพ่สองใบจะถูกแทรกโดยมีหมายเลข 1 ติดอยู่ ตอนนี้ ในเกม เราต้องรวบรวมคะแนนสูงสุดโดยหยิบไพ่ที่กำหนด การ์ดจะแสดงใน 'การ์ด' ของอาร์เรย์ โดยที่องค์ประกอบในอาร์เรย์แสดงถึงจำนวนการ์ด[i] เมื่อเราหยิบไพ่ 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
- สำหรับ z ในช่วง x + 1 ถึง y ทำ
- อุณหภูมิ :=สูงสุดของ (ชั่วคราว ค้นหา (x, z) + ค้นหา (z, y) + การ์ด[x] * การ์ด[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
