ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ
แก้ปัญหาระเบิดลูกโป่งด้วยการคิดย้อนกลับ โดยเลือกว่าจะระเบิดลูกโป่งใดเป็นลูกสุดท้ายในแต่ละช่วง แทนที่จะเลือกลูกแรก
ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
โจทย์การทำให้ลูกโป่งแตก
เมื่อกำหนดลูกโป่ง n ลูกที่มีค่า nums การทำให้ลูกโป่ง i แตกจะได้เหรียญ nums[i-1] * nums[i] * nums[i+1] (ผลคูณของตัวมันเองกับลูกโป่งข้างเคียงในขณะนั้น) หลังจากลูกโป่งแตก ลูกโป่งข้างเคียงจะมาอยู่ติดกัน จงหาจำนวนเหรียญสูงสุดที่สามารถเก็บได้จากการทำให้ลูกโป่งทั้งหมดแตก การจำลองแบบตรงไปตรงมาทำได้ยาก เพราะการทำให้ลูกโป่งแตกจะเปลี่ยนลูกโป่งข้างเคียง — DP แบบช่วงย้อนกลับ ช่วยหลีกเลี่ยงความยุ่งยากนี้ได้อย่างสง่างาม
เหตุใดการจำลองไปข้างหน้าจึงใช้ไม่ได้
หากเราลองกำหนดให้ dp[i][j] เป็นจำนวนเหรียญสูงสุดจากการทำให้ลูกโป่งในช่วง [i, j] แตก และพิจารณาว่าควรทำให้ลูกโป่งใดแตกก่อน เราจะพบปัญหาว่า หากทำให้ลูกโป่ง k แตกก่อน nums[k-1] และ nums[k+1] ต้องเป็นลูกโป่งข้างเคียงในขณะนั้น แต่ลูกโป่งเหล่านั้นอาจถูกทำให้แตกภายหลัง ซึ่งจะทำให้ลูกโป่งข้างเคียงเปลี่ยนไปตามลำดับ สถานะจึงกำหนดให้ชัดเจนได้ยากเมื่อมองในทิศทางไปข้างหน้า
แนวคิดสำคัญ: คิดย้อนกลับ
เคล็ดลับคือให้พิจารณาว่าลูกโป่งใดจะเป็นลูกสุดท้ายที่แตกในช่วง [i, j] เมื่อลูกโป่ง k เป็นลูกสุดท้ายที่แตกใน [i, j] ลูกโป่งอื่นทั้งหมดใน [i, j] จะหายไปแล้ว ดังนั้นลูกโป่ง k จึงมีลูกโป่งข้างเคียงเป็น nums[i-1] และ nums[j+1] พอดี ซึ่งเป็นลูกโป่งขอบเขตที่อยู่นอกช่วง การคำนวณเหรียญสำหรับการทำให้ลูกสุดท้ายแตกจึง แน่นอนตายตัว และไม่ขึ้นอยู่กับลำดับการทำให้ลูกอื่นแตกก่อนหน้า
การกำหนดสถานะและสมการเวียนเกิด
เพิ่มลูกโป่งตัวคั่น: เติม 1 ไว้ด้านหน้าและด้านท้ายของ nums เพื่อสร้าง nums = [1] + nums + [1] กำหนดให้ dp[i][j] เป็นจำนวนเหรียญสูงสุดจากการทำให้ลูกโป่งทั้งหมดที่อยู่ระหว่างดัชนี i และ j แตก โดยไม่รวมปลายทั้งสอง และให้ nums[i] กับ nums[j] เป็นลูกโป่งขอบเขตที่ยังเหลืออยู่ สมการเวียนเกิดคือ สำหรับลูกโป่งตัวสุดท้ายที่เป็นไปได้แต่ละตัว k ใน (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
# With sentinels: nums = [1] + original + [1]
# dp[i][j] = max coins from bursting all balloons in open interval (i, j)
# k = last balloon to burst in (i,j)
# dp[i][j] = max over k in (i,j): dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]การนำไปใช้งานฉบับเต็ม
เราเติมอาร์เรย์ด้วยตัวคั่น กำหนดค่าเริ่มต้นของตาราง DP เป็นศูนย์ (ช่วงว่างมีเหรียญเป็น 0) และเติมค่าตามความยาวช่วงที่เพิ่มขึ้น คำตอบสุดท้ายคือ dp[0][n+1] ซึ่งแทนจำนวนเหรียญสูงสุดจากการทำให้ลูกโป่งเดิมทั้งหมดแตก โดยมีตัวคั่นเป็นขอบเขตถาวร
def maxCoins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0]*n for _ in range(n)]
# length of open interval (i, j) exclusive: j - i - 1 balloons inside
for length in range(2, n): # length = j - i
for i in range(0, n - length):
j = i + length
for k in range(i+1, j): # k is last burst in (i, j)
coins = dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
dp[i][j] = max(dp[i][j], coins)
return dp[0][n-1]
print(maxCoins([3, 1, 5, 8])) # 167การไล่ดูตัวอย่าง
สำหรับ [3, 1, 5, 8] เมื่อเติมตัวคั่นจะได้ [1, 3, 1, 5, 8, 1] (ดัชนี 0-5) เราต้องการ dp[0][5] สำหรับช่วง length=2 (มีลูกโป่งอยู่ภายในหนึ่งลูก): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40 เมื่อคำนวณต่อไป คำตอบที่ดีที่สุดคือทำให้ 1 เป็นลูกสุดท้ายที่แตกในกลุ่ม {3,1,5,8} หลังจากทำให้ลูกโป่งข้างเคียงแตกก่อน ทำให้ได้เหรียญรวม 167 เหรียญ
การวิเคราะห์ความซับซ้อน
มี ช่วง O(n²) ช่วง และสำหรับแต่ละช่วง เราลอง จุดแบ่ง O(n) จุด จึงมี ความซับซ้อนด้านเวลา O(n³) พื้นที่ที่ใช้คือ O(n²) สำหรับตาราง DP สำหรับลูกโป่ง n = 500 ลูก จะมีการดำเนินการ 125 ล้านครั้ง ซึ่งยังทำได้ภายใต้ข้อจำกัดของการสัมภาษณ์ การเติมตัวคั่นช่วยให้จัดการขอบเขตได้ง่ายขึ้น หากไม่มีตัวคั่น คุณจะต้องตรวจสอบโดยตรงว่า i-1 และ j+1 อยู่ภายในขอบเขตหรือไม่
ทางเลือกแบบจากบนลงล่างที่ใช้การจดจำผลลัพธ์
เราสามารถเขียนวิธีแก้แบบเดียวกันจากบนลงล่างโดยใช้ @lru_cache ซึ่งอาจทำความเข้าใจและอนุมานได้ง่ายกว่าในการสัมภาษณ์ กำหนดให้ solve(i, j) เป็นจำนวนเหรียญสูงสุดในช่วงเปิด (i, j) ฟังก์ชันจะลองให้ k ทุกค่าทำหน้าที่เป็นลูกสุดท้ายที่แตก และจดจำผลลัพธ์ไว้ ทั้งสองแนวทางมีความซับซ้อนด้านเวลาและพื้นที่เท่ากัน
from functools import lru_cache
def maxCoins_memo(nums):
nums = [1] + nums + [1]
n = len(nums)
@lru_cache(maxsize=None)
def solve(i, j):
if j - i < 2: # no balloons between i and j
return 0
return max(
solve(i, k) + solve(k, j) + nums[i]*nums[k]*nums[j]
for k in range(i+1, j)
)
return solve(0, n-1)
print(maxCoins_memo([3, 1, 5, 8])) # 167ข้อผิดพลาดที่พบบ่อย: การกำหนด DP แบบไปข้างหน้า
ข้อผิดพลาดที่พบบ่อยคือกำหนดให้ dp[i][j] เป็นจำนวนเหรียญเมื่อทำให้ลูกโป่งตัวแรกใน [i,j] แตก แทนที่จะเป็นลูกสุดท้าย วิธีนี้ใช้ไม่ได้ เพราะการคำนวณเหรียญสำหรับการทำให้ลูกแรกแตกขึ้นอยู่กับลูกโป่งข้างเคียงที่ยังไม่ถูกทำให้แตก และสถานะของลูกโป่งข้างเคียงเหล่านั้นจะเปลี่ยนไปเมื่ออัลกอริทึมดำเนินต่อไป เมื่อขอบเขตขึ้นอยู่กับองค์ประกอบที่ยังเหลืออยู่ ใน DP แบบช่วงควรคิดถึง องค์ประกอบสุดท้าย เสมอ
เหตุใดค่าตัวคั่นจึงเป็น 1
เลือกตัวคั่นที่มีค่า 1 เพราะทำหน้าที่เป็น สมาชิกเอกลักษณ์ของการคูณ เมื่อลูกโป่งขอบเขตเป็นลูกสุดท้ายที่แตก ค่าของเหรียญจะเป็น boundary * last * boundary = 1 * last * 1 = last หากใช้ 0 จะได้เหรียญเป็น 0 ซึ่งไม่ถูกต้อง และหากใช้ค่าอื่นจะทำให้การคำนวณคลาดเคลื่อน เทคนิคการใช้ตัวคั่นช่วยรวมกรณีขอบเขตทั้งหมดเข้าด้วยกันอย่างเป็นระเบียบ โดยไม่ต้องเขียนกรณีพิเศษสำหรับลูกโป่งซ้ายสุดและขวาสุด
เปรียบเทียบกับ DP แบบช่วงมาตรฐาน
ใน DP แบบช่วงมาตรฐาน (การคูณสายเมทริกซ์) จุดแบ่ง k แทนตำแหน่งที่เราแบ่งโจทย์ออกเป็นโจทย์ย่อยสองส่วน ซึ่งแก้ แยกจากกัน ในโจทย์ Burst Balloons k คือ ลูกสุดท้ายที่จะแตกในช่วง ทำให้ช่วงย่อย [i,k] และ [k,j] เป็นอิสระต่อกัน โดยมีเงื่อนไขว่า k ยังคงอยู่เป็นขอบเขต มุมมองแบบย้อนกลับนี้คือแนวคิดสร้างสรรค์ที่ทำให้สามารถแก้โจทย์การทำให้ลูกโป่งแตกด้วย DP แบบช่วงได้
ตรวจสอบอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
ทบทวนบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า: การจำลองไปข้างหน้าล้มเหลว เนื่องจากการระเบิดลูกโป่งทำให้เพื่อนบ้านเปลี่ยนแปลงอย่างคาดเดาไม่ได้, แนวคิดย้อนกลับกำหนดให้ k เป็นลูกโป่งลูกสุดท้ายที่ถูกระเบิดในช่วง ทำให้เพื่อนบ้านเป็น nums[i] และ nums[j], และ สมการเวียนเกิด dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) พร้อมการเติมค่าขอบเขตพิเศษ ทำให้ได้วิธีแก้ปัญหาความซับซ้อน O(n³) บทถัดไป เราจะเปลี่ยนไปเรียนรู้ DP สำหรับปัญหากระเป๋าเป้ โดยเริ่มจากกระเป๋าเป้ 0/1 แบบคลาสสิกและการลดการใช้หน่วยความจำ
คำถามที่พบบ่อย
บทเรียน “ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ”
แก้ปัญหาระเบิดลูกโป่งด้วยการคิดย้อนกลับ โดยเลือกว่าจะระเบิดลูกโป่งใดเป็นลูกสุดท้ายในแต่ละช่วง แทนที่จะเลือกลูกแรก คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- รูปแบบ DP แบบช่วงและลำดับการเติมค่า
- ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด
- การแบ่งพาลินโดรม II
- ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ