Dynamic Programming (DP) หลายมิติ — พื้นฐาน & แนวคิด

ในหมวดก่อน dynamic programming (DP) ของเราใช้ state (สถานะ) แค่ตัวเดียว (dp[i]) แต่หลายโจทย์มีตัวแปรที่เปลี่ยนพร้อมกันสองอย่าง เช่นกำลังดูตัวอักษร index (ตำแหน่ง) ที่ i ของ string (สตริง) แรก และ index ที่ j ของ string ที่สอง หรือกำลังยืนอยู่ที่ row (แถว) i, column (คอลัมน์) j ของ grid (กริด) กรณีแบบนี้ state เดียวไม่พอ เราต้องใช้ 2D table (ตาราง 2 มิติ) dp[i][j] แทน แต่ไอเดียหลักยังเหมือนเดิมเป๊ะ: define (นิยาม) state ให้ชัด หา transition (สูตรเปลี่ยนสถานะ) แล้ว iterate (วน) เติม table

dp[i][j] คืออะไร — state บนตาราง

DP หลายมิติคือการขยาย state จากเส้นเดียวเป็น table dp[i][j] หมายถึงคำตอบของ subproblem (ปัญหาย่อย) ที่ระบุด้วย index สองตัว i และ j โจทย์ที่เข้าข่ายมักมีสองหน้าตา: (1) two strings / two sequences (สองสตริง/สองลำดับ) เช่นเทียบ word1 กับ word2 โดย i วิ่งบน word1 และ j วิ่งบน word2 หรือ (2) grid เช่นเดินบน table ขนาด m x n โดย i คือ row, j คือ column

วิธีคิด transition คือถามว่าช่อง dp[i][j] คำนวณได้จากช่องข้างเคียงตัวไหน โดยทั่วไปเป็นเพื่อนบ้านสามช่อง: บน dp[i-1][j], ซ้าย dp[i][j-1], และทแยงบนซ้าย dp[i-1][j-1] เรา iterate เติม table จากซ้ายบนไปขวาล่าง เพื่อให้ตอนคำนวณช่องหนึ่ง ช่องที่มันต้องพึ่งพาถูกเติมไว้ก่อนแล้ว

# template DP 2 มิติ (นิยมเผื่อแถว/คอลัมน์ที่ 0 ไว้เป็น base case)
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]   # ตาราง (m+1) x (n+1)

# เติม base case ที่ขอบ (dp[0][*] และ dp[*][0]) ตามโจทย์
# ...

for i in range(1, m + 1):
    for j in range(1, n + 1):
        # dp[i][j] คำนวณจากเพื่อนบ้าน: บน / ซ้าย / ทแยง
        dp[i][j] = f(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

answer = dp[m][n]   # มุมขวาล่างมักเป็นคำตอบ