รูปแบบ DP แบบช่วงและลำดับการเติมค่า
กำหนดสถานะ DP แบบช่วง dp[i][j] อธิบายเหตุผลที่ต้องเติมค่าช่วงตามลำดับความยาวที่เพิ่มขึ้น และติดตามรูปแบบกับการคูณสายโซ่เมทริกซ์
รูปแบบ DP แบบช่วงและลำดับการเติมค่า เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
DP แบบช่วงคืออะไร
DP แบบช่วง เป็นรูปแบบการเขียนโปรแกรมพลวัตที่สถานะ dp[i][j] แทนคำตอบที่ดีที่สุดสำหรับปัญหาย่อยซึ่งครอบคลุมดัชนีตั้งแต่ i ถึง j แนวคิดสำคัญคือ เราแก้ช่วงที่เล็กกว่าก่อน แล้วค่อยสร้างคำตอบจนเต็มช่วง รูปแบบนี้เหมาะกับการจำลองปัญหาอย่างการคูณเมทริกซ์แบบสายโซ่ การแบ่งพาร์ทิชันพาลินโดรม และการทำให้ลูกโป่งแตก ซึ่งขอบเขตของปัญหาย่อยคือจุดปลายซ้ายและขวาของช่วง
คำจำกัดความของสถานะและกรณีฐาน
สำหรับ DP แบบช่วง สถานะ คือ dp[i][j] โดยที่ i <= j ส่วน กรณีฐาน คือช่วงที่มีองค์ประกอบเดียว: dp[i][i] กรณีเหล่านี้แก้ได้โดยตรง — ตัวอย่างเช่น เมทริกซ์เดียวมีต้นทุนการคูณเป็นศูนย์ ช่วงที่มีองค์ประกอบสองตัว dp[i][i+1] ก็มักมีคำตอบที่เรียบง่ายเช่นกัน เราเติมตารางตามความยาวช่วงที่เพิ่มขึ้น โดยเริ่มจากความยาว 1 จนถึง n
n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
dp[i][i] = 0 # length-1 intervalsลำดับการเติม: ความยาวเพิ่มขึ้น
รายละเอียดสำคัญของ DP แบบช่วงคือลำดับการเติม เราต้องคำนวณช่วงทั้งหมดที่มีความยาว L ก่อนคำนวณช่วงที่มีความยาว L+1 เนื่องจากช่วงที่ยาวกว่าจะขึ้นอยู่กับช่วงย่อยที่สั้นกว่า ลูปชั้นนอกจะวนตามความยาวช่วงตั้งแต่ 2 ถึง n ลูปชั้นกลางกำหนดขอบเขตซ้าย i และเราหาขอบเขตขวาได้จาก j = i + L - 1
n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for length in range(2, n + 1): # interval length
for i in range(n - length + 1): # left boundary
j = i + length - 1 # right boundary
for k in range(i, j): # split point
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])การตั้งค่าการคูณเมทริกซ์แบบสายโซ่
ปัญหา DP แบบช่วงคลาสสิกคือ การคูณเมทริกซ์แบบสายโซ่: เมื่อกำหนดเมทริกซ์ที่มีมิติ dims[0..n] ให้หาจำนวนการคูณสเกลาร์ขั้นต่ำที่ใช้ในการคำนวณผลคูณ การคูณเมทริกซ์ A(p×q) ด้วย B(q×r) มีต้นทุน p*q*r การดำเนินการ dp[i][j] = ต้นทุนขั้นต่ำในการคูณเมทริกซ์ตั้งแต่ i ถึง j จุดแบ่ง k เป็นตัวกำหนดว่าจะตัดลำดับออกเป็นสายโซ่ย่อยสองส่วนที่ใด
def matrix_chain_order(dims):
n = len(dims) - 1 # number of matrices
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
print(matrix_chain_order([10, 30, 5, 60])) # 4500การไล่ดูตาราง DP
ลองไล่ดูตัวอย่างการคูณเมทริกซ์แบบสายโซ่ที่มีมิติ [10, 30, 5, 60] ซึ่งแทนเมทริกซ์สามตัว ได้แก่ A(10×30) B(30×5) และ C(5×60) สำหรับ dp[0][2] เราลองแบ่งที่ k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000 และที่ k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500 ดังนั้น dp[0][2] = 4500 ซึ่งได้จากการคูณ AB ก่อน
เหตุใดลำดับการเติมนี้จึงใช้ได้
เมื่อคำนวณ dp[i][j] เราจะอ้างอิง dp[i][k] และ dp[k+1][j] สำหรับทุกค่า k ใน [i, j-1] ช่วงย่อยทั้งสองมีความยาวน้อยกว่าอย่างเคร่งครัดเมื่อเทียบกับ [i, j] การวนตามความยาวจากน้อยไปมากทำให้ช่วงย่อยที่จำเป็นทั้งหมดถูกคำนวณไว้ก่อนที่เราจะต้องใช้ นี่คือเหตุผลด้านความถูกต้องพื้นฐานของลำดับการเติม DP แบบช่วง — ช่วงที่สั้นกว่าจะเป็นสิ่งที่ช่วงที่ยาวกว่าต้องพึ่งพาเสมอ
DP แบบช่วงจากบนลงล่างโดยใช้การจดจำผลลัพธ์
อีกทางเลือกหนึ่งคือการใช้ DP แบบช่วงแบบจากบนลงล่างร่วมกับการจดจำผลลัพธ์ เราเขียนฟังก์ชันเรียกซ้ำ solve(i, j) ซึ่งคืนต้นทุนที่ดีที่สุดสำหรับช่วง [i, j] และเก็บผลลัพธ์ไว้ในพจนานุกรม ลำดับการเติมจะถูกจัดการโดยการเรียกซ้ำโดยอัตโนมัติ วิธีจากบนลงล่างมักทำความเข้าใจได้ง่ายกว่า แต่อาจมีต้นทุนจากการเรียกใช้ฟังก์ชัน ส่วนวิธีจากล่างขึ้นบนจะเร็วกว่าในทางปฏิบัติเมื่อข้อมูลนำเข้ามีขนาดใหญ่
from functools import lru_cache
def matrix_chain_memo(dims):
n = len(dims) - 1
@lru_cache(maxsize=None)
def solve(i, j):
if i == j:
return 0
return min(
solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
for k in range(i, j)
)
return solve(0, n-1)
print(matrix_chain_memo([10, 30, 5, 60])) # 4500ความซับซ้อนด้านเวลาและพื้นที่
DP แบบช่วงมีสถานะ O(n²) ซึ่งครอบคลุมคู่ทั้งหมด (i, j) และแต่ละสถานะจะวนผ่านจุดแบ่ง O(n) จุด จึงมีtime O(n³) โดยรวม ใช้พื้นที่ O(n²) สำหรับตาราง DP สำหรับการคูณเมทริกซ์แบบสายโซ่ที่มีเมทริกซ์ 100 ตัว จะมีการดำเนินการ 1,000,000 ครั้ง ซึ่งทำได้อย่างสบาย รูปแบบนี้ปรากฏในปัญหา LeetCode ยาก ๆ มากมาย และเป็นที่ชื่นชอบในการสัมภาษณ์ของ FAANG เนื่องจากมีโครงสร้างที่ไม่เห็นได้ชัดในทันที
การสร้าง solution ที่ดีที่สุดกลับคืนมา
หากต้องการสร้างการใส่วงเล็บจริงกลับคืนมา ไม่ใช่เพียงต้นทุน ให้เก็บตาราง split[i][j] แยกต่างหากเพื่อบันทึกว่า k ใดทำให้แต่ละสถานะมีค่าต่ำสุด จากนั้นอ่านจุดแบ่งกลับคืนมาแบบเรียกซ้ำ: reconstruct(i, j) จะแสดงการจัดกลุ่มที่ดีที่สุดโดยเรียกซ้ำกับ [i, split[i][j]] และ [split[i][j]+1, j] เทคนิคนี้ใช้ได้กับปัญหา DP แบบช่วงทั้งหมด
def matrix_chain_with_split(dims):
n = len(dims) - 1
dp = [[0]*n for _ in range(n)]
split = [[0]*n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp[0][n-1], splitแม่แบบสำหรับปัญหา DP แบบช่วงทุกประเภท
แม่แบบสากลของ DP แบบช่วงมีสามส่วน: (1) กำหนดค่ากรณีฐานสำหรับองค์ประกอบเดี่ยว (2) วนตามความยาวที่เพิ่มขึ้น และสำหรับแต่ละความยาวให้วนตามขอบเขตซ้ายที่ใช้ได้ พร้อมคำนวณขอบเขตขวา และ (3) สำหรับแต่ละช่วง ให้วนผ่านจุดแบ่งทั้งหมดแล้วใช้สมการเวียนเกิดเฉพาะของปัญหา สิ่งเดียวที่เปลี่ยนไปในแต่ละปัญหาคือสูตรสมการเวียนเกิดภายในลูปด้านในสุด
def interval_dp_template(n, base_cost, split_cost):
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = base_cost(i) # problem-specific base case
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
# problem-specific recurrence
candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
dp[i][j] = min(dp[i][j], candidate)
return dp[0][n-1]ปัญหา DP แบบช่วงที่พบบ่อย
ปัญหาที่ใช้ DP แบบช่วง ได้แก่: การคูณเมทริกซ์แบบสายโซ่ (ลดจำนวนการดำเนินการให้ต่ำสุด) การทำให้ลูกโป่งแตก (เพิ่มจำนวนเหรียญให้สูงสุด) เครื่องพิมพ์พิสดาร (ลดจำนวนการดำเนินการพิมพ์ให้ต่ำสุด) การหาสามเหลี่ยมที่มีคะแนนต่ำสุดของรูปหลายเหลี่ยม และ การแบ่งพาร์ทิชันพาลินโดรม II แต่ละปัญหาใช้โครงสร้างลำดับการเติมแบบเดียวกัน แต่ใช้สมการเวียนเกิดต่างกัน จงสังเกตรูปแบบนี้เมื่อปัญหาถามหาค่าที่ดีที่สุดบนช่วงหรือลำดับ ซึ่งสามารถแบ่งได้ที่จุดภายในใด ๆ
ตรวจสอบความเข้าใจอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดจากบทเรียนนี้ในรายวิชาโครงสร้างข้อมูล & อัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรม
สรุปบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า DP แบบช่วงใช้ dp[i][j] เพื่อแทนคำตอบที่ดีที่สุดบนช่วงหนึ่ง ลำดับการเติมต้องเรียงตามความยาวช่วงที่เพิ่มขึ้น เพื่อให้คำนวณช่วงย่อยก่อน และ แม่แบบสากลมี time O(n³) และใช้พื้นที่ O(n²) บทถัดไปเราจะสำรวจลำดับย่อยและสตริงย่อยแบบพาลินโดรมที่ยาวที่สุดโดยใช้รูปแบบนี้
คำถามที่พบบ่อย
บทเรียน “รูปแบบ DP แบบช่วงและลำดับการเติมค่า” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “รูปแบบ DP แบบช่วงและลำดับการเติมค่า” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “รูปแบบ DP แบบช่วงและลำดับการเติมค่า”
กำหนดสถานะ DP แบบช่วง dp[i][j] อธิบายเหตุผลที่ต้องเติมค่าช่วงตามลำดับความยาวที่เพิ่มขึ้น และติดตามรูปแบบกับการคูณสายโซ่เมทริกซ์ คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “รูปแบบ DP แบบช่วงและลำดับการเติมค่า” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- รูปแบบ DP แบบช่วงและลำดับการเติมค่า
- ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด
- การแบ่งพาลินโดรม II
- ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ