"Dynamic Programming is recursion without repetition"
• เป็นเทคนิคที่รวม **ความถูกต้อง** ของ Complete Search เข้ากับ **ประสิทธิภาพ** ของ Greedy Algorithms
• ใช้สำหรับแก้ปัญหาที่สามารถแบ่งเป็น **ปัญหาย่อยที่ทับซ้อนกัน (Overlapping Subproblems)**
• หัวใจหลักคือการเก็บคำตอบของปัญหาย่อยไว้เพื่อไม่ให้ต้องคำนวณซ้ำ (Reuse)
ปัญหาใหญ่ประกอบด้วยปัญหาย่อยชุดเดิมที่ถูกเรียกซ้ำไปมาหลายครั้ง หากวาด Recursion Tree จะพบกิ่งก้านที่คำนวณค่าเดิมซ้ำๆ
คำตอบที่เหมาะสมที่สุดของปัญหาใหญ่ สามารถสร้างขึ้นได้จากคำตอบที่เหมาะสมที่สุดของปัญหาย่อย
แนวคิด: เขียน Recursion ตามปกติ แต่เพิ่ม **"สมุดจด" (Table/Array)** ไว้บันทึกผลลัพธ์
แนวคิด: เติมตารางคำตอบอย่างจงใจ (Fill Deliberately) เริ่มจากกรณีพื้นฐานที่สุดขึ้นไป
สูตรเวียนเกิด: \(f(n) = f(n-1) + f(n-2)\) โดยมี \(f(0)=0, f(1)=1\)
ปัญหาของ Naive Recursion:
การคำนวณ \(f(n)\) จะมีการเรียกฟังก์ชันซ้ำซ้อนมหาศาล เช่น \(f(5)\) ต้องเรียก \(f(3)\) สองครั้ง และ \(f(2)\) สามครั้ง... ทำให้ความซับซ้อนพุ่งสูงถึง \(O(2^n)\)
// การจดจำผลลัพธ์ลงในอาเรย์
long long memo[56];
long long f(int n) {
if (n <= 1) return n; // Base Case
if (memo[n] != -1) return memo[n]; // คืนค่าที่จดไว้
return memo[n] = f(n-1) + f(n-2); // คำนวณแล้วจด
}
ความซับซ้อนลดเหลือ \(O(n)\) เพราะคำนวณแต่ละสถานะเพียงครั้งเดียว
// การเติมตารางจากล่างขึ้นบน
long long dp[56];
dp = 0; dp[59] = 1; // เริ่มจากกรณีพื้นฐาน
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // สร้างคำตอบใหม่จากคำตอบเก่า
}
return dp[n];
ใช้พื้นที่ \(O(n)\) และเวลา \(O(n)\) โดยไม่มีความเสี่ยงเรื่อง Stack Overflow
หัวใจของการเปลี่ยนปัญหาใหญ่เป็นปัญหาย่อย
• **สถานะ (State)**: คือชุดของพารามิเตอร์ที่เพียงพอจะบอกลักษณะของปัญหาย่อยนั้นๆ
• ในปัญหาการทอนเหรียญ (Coin Problem) สถานะคือ **"มูลค่าที่เหลือที่ต้องทอน"**
• สถานะที่ออกแบบได้ดีจะช่วยลดจำนวนปัญหาย่อยที่ซ้ำซ้อนและประหยัดหน่วยความจำ
หากพิจารณาการทอนเหรียญมูลค่า 10 ด้วยเหรียญ {1, 3, 4} เราจะพบว่ามีการเรียก solve(6) หรือ solve(7) ซ้ำไปมาหลายกิ่งก้าน
"ใน DP เราจะไม่ยอมเสียเวลาคำนวณค่าเดิมเป็นรอบที่สอง"
ปัญหา DP ทุกปัญหา สามารถเขียนให้อยู่ในรูปของ **DAG** ได้:
1. ตรวจสอบอาเรย์ ready[x] ว่าเป็นจริงหรือไม่
2. ถ้าเคยคำนวณแล้ว (True) ดึงค่าจาก value[x] ส่งกลับทันที
3. ถ้ายังไม่เคยทำ ให้คำนวณตามสูตร Recursion และเก็บผลลัพธ์ลงในตารางก่อน return
• ลืมตั้งค่าเริ่มต้นให้ตาราง (เช่น ตั้งเป็น -1 หรือ INF)
• ไม่เก็บค่าลงตารางก่อนจบฟังก์ชัน ทำให้ความซับซ้อนยังคงเป็น Exponential
• ขอบเขตของอาเรย์ไม่เพียงพอสำหรับสถานะที่เป็นไปได้ทั้งหมด
"Filling the table deliberately"
dp = 0)
เราต้องเติมตารางตามลำดับที่ทำให้ "ปัญหาย่อยถูกแก้ก่อนปัญหาใหญ่เสมอ"
เติมจาก 0 ไปถึง N (เช่น Fibonacci, Coin Problem)
เติมทีละแถว (Row-major) หรือตามเส้นทแยงมุม
มักใช้ Post-order Traversal (ทำลูกก่อนทำพ่อ)
Arrays (1D/2D/3D)
ได้รับความนิยมสูงสุดเนื่องจากเข้าถึงค่าได้เร็วในเวลา \(O(1)\)
Map (BST or Hash Table)
ใช้เมื่อสถานะมีความเบาบาง (Sparse States) หรือเป็นข้อมูลที่ซับซ้อน เช่น String
"คำตอบที่ดีที่สุดของปัญหาใหญ่ มาจากคำตอบที่ดีที่สุดของปัญหาย่อย"
• ในปัญหา **Coin Change**: คำตอบของ solve(x) ย่อมมาจากค่าที่น้อยที่สุดของ solve(x-c) เสมอ
• หากปัญหาขาดคุณสมบัตินี้ (เช่น ปัญหาที่คำตอบย่อยขัดแย้งกันเอง) เราจะไม่สามารถใช้ DP ได้อย่างตรงไปตรงมา
Time Complexity = จำนวนสถานะ × งานที่ทำในแต่ละสถานะ
สถานะ: \(n\) (เป้าหมาย)
งานต่อสถานะ: \(k\) (จำนวนเหรียญ)
**รวม: \(O(nk)\)**
สถานะ: \(n \times n\) (ตาราง)
งานต่อสถานะ: \(O(1)\) (เลือก บน/ซ้าย)
**รวม: \(O(n^2)\)**
นอกจากหา "ค่าสูงสุด/ต่ำสุด" แล้ว โจทย์มักต้องการ "เลือกอะไรบ้าง?"
first[x] = เหรียญแรกที่ทำให้ solve(x) มีค่าน้อยที่สุด
เราใช้อาเรย์เสริม (เช่น first[x]) เพื่อบันทึก **"การตัดสินใจที่เหมาะสมที่สุด"** ในแต่ละสถานะ จากนั้นใช้ลูปดึงข้อมูลย้อนกลับ (Reconstruct) เพื่อสร้างลำดับคำตอบที่สมบูรณ์
ผลลัพธ์ของปัญหา DP มักมีค่าเพิ่มขึ้นอย่างรวดเร็ว .
• ประเภทข้อมูล int เก็บค่าได้เพียงประมาณ \(2 \cdot 10^9\) เท่านั้น .
• ควรใช้ long long สำหรับเก็บสถานะ DP เพื่อป้องกันค่าเกินขอบเขต .
• **จุดที่มักพลาด**: การคูณเลข int สองตัวก่อนจะเก็บเข้าตัวแปร long long จะทำให้เกิด Overflow ก่อนเสมอ .
"บางปัญหาไม่ได้ต้องการคำตอบที่แท้จริง แต่ต้องการเศษจากการหารด้วย \(10^9+7\)" .
• คุณสมบัตินี้ช่วยให้นักโปรแกรมสามารถหา Modulo ในทุกขั้นตอนการคำนวณเพื่อไม่ให้ค่าตัวแปรใหญ่เกินไป .
มักเกิดขึ้นเมื่อพยายามเข้าถึง dp[x-c] โดยที่ x-c < 0 นักเขียนโปรแกรมต้องตรวจสอบเงื่อนไขก่อนเรียกเสมอ .
การลืมล้างค่าในตาราง memo (เช่น ลืมตั้งเป็น -1) หรือตั้งค่าเริ่มต้นในตาราง dp ผิดพลาดสำหรับกรณีพื้นฐาน (Base Cases) .
แนวคิด: "ไม่จำเป็นต้องจำทุกอย่างที่คำนวณมาแล้ว" .
• ใน Iterative DP เราสามารถลดพื้นที่จาก \(O(n)\) เหลือ \(O(k)\) ได้ หากค่าปัจจุบันพึ่งพาเพียง \(k\) สถานะก่อนหน้า .
• ตัวอย่าง: Fibonacci พึ่งพาเพียง 2 ค่าก่อนหน้า ดังนั้นเราสามารถเก็บเพียง 2 ตัวแปรเพื่อคำนวณค่าถัดไปได้ในพื้นที่ \(O(1)\) .
สำหรับปัญหาตาราง \(n \times m\) :
dp[i] พึ่งพาเพียงแถวก่อนหน้า dp[i-1]..."Topological Ordering of states" .
ในการเขียน Bottom-up DP คุณต้องมั่นใจว่า **ปัญหาย่อยต้องถูกคำนวณก่อนปัญหาใหญ่เสมอ** :
ในบางปัญหาที่มีสถานะจำนวนมหาศาล (เช่น Subset Sum ที่เป้าหมาย \(T\) มีค่าใหญ่มาก) การเขียนตาราง DP ทั้งหมดอาจช้ากว่าการเรียก Recursion ปกติ .
"การสร้างตารางสำหรับสถานะที่ Recursion ไม่เคยเรียกใช้เลย เป็นการเสียเวลาและหน่วยความจำโดยใช่เหตุ" .
ถ้าต้องเลือกความเหมาะสมที่สุด (Optimization) ให้ระวัง Greedy .
• Greedy มักจะให้คำตอบที่รวดเร็วแต่ **ไม่ถูกต้อง** สำหรับปัญหาที่มีโครงสร้างซับซ้อน .
• ในการแข่งขันโอลิมปิก หากคุณคิดถึงคำว่า "Greedy" จิตใต้สำนึกของคุณกำลังบอกให้ใช้ "Dynamic Programming" .
บางครั้งพารามิเตอร์หนึ่งสามารถคำนวณได้จากพารามิเตอร์อื่นที่เหลืออยู่ .
ตัวอย่าง: ปัญหาการบรรทุกรถลงเรือ 4 เลน หากเรารู้ความยาวรถที่ใช้ไปรวมทั้งหมด (\(U\)) และความยาวที่จอดไปแล้วใน 3 เลนแรก เราย่อมรู้ความยาวในเลนที่ 4 ทันทีโดยไม่ต้องส่งพารามิเตอร์เพิ่ม .
การลดสถานะที่ไม่จำเป็นช่วยลดขนาดตาราง DP ได้จากระดับ \(O(N \cdot L^4)\) ลงเหลือ \(O(L^4)\) ซึ่งประหยัดทรัพยากรอย่างมหาศาล .
"Dynamic Programming is not about filling in tables.
It's about smart recursion!"
✓ เริ่มจาก Recursion ที่ถูกต้อง .
✓ เลือกการจดจำ (Memoization) ที่เหมาะสม .
✓ ตรวจสอบความถูกต้องของลำดับการคำนวณ .
✓ ปรับปรุงพื้นที่จัดเก็บเมื่อทำได้ .
ลำดับการคำนวณที่เปลี่ยนไป
• สำหรับปัญหาที่เกี่ยวกับช่วง ลำดับการคำนวณมักจะเริ่มจากช่วงที่มีความยาวน้อยที่สุดก่อนแล้วค่อยขยายไปยังช่วงที่ยาวขึ้น .
• การเลือกพารามิเตอร์ที่ถูกต้องและตัดข้อมูลที่ซ้ำซ้อนออกจะช่วยลดจำนวนสถานะลงได้อย่างมหาศาล .
การทำ DP บน Trees มักต้องการการท่องไปในโหนดแบบ **Post-order traversal** . วิธีนี้ช่วยให้ปัญหาย่อยที่ระดับล่าง (Leaf nodes) ถูกแก้ไขก่อนที่คำตอบจะถูกส่งกลับไปยังโหนดพ่อ .
"คำนวณเฉพาะสิ่งที่จำเป็นเท่านั้น"
• ข้อดีสำคัญของ Top-down DP คือฟังก์ชันจะเลือกคำนวณเฉพาะสถานะที่สามารถเข้าถึงได้จากจุดเริ่มต้นจริงเท่านั้น .
• ในบางปัญหาที่มีสถานะที่ "เป็นไปได้" ตามทฤษฎีจำนวนมาก แต่มีการใช้งานจริงเพียงเล็กน้อย วิธีนี้จะประหยัดเวลาได้มากกว่าการวนลูปทุกสถานะแบบ Bottom-up .
ระวังการออกแบบสถานะที่ใหญ่เกินไป!
ในปัญหา **Ferry Loading** หากเราใช้สถานะเป็นความยาวของทั้ง 4 เลน อาเรย์จะมีขนาดใหญ่จนหน่วยความจำไม่พอ .
เทคนิค: เนื่องจากเรารู้ความยาวรถรวมทั้งหมด หากเรารู้ความยาวของ 3 เลนแรก เราย่อมคำนวณเลนที่ 4 ได้ทันที ทำให้ลดมิติของ DP ลงได้อย่างมหาศาล .
หัวใจสำคัญของสถานะ DP คือการที่เราไม่สนใจลำดับการเลือกในอดีตว่า "ทำอย่างไร" ถึงมาถึงจุดนี้ .
ข้อมูลที่เก็บไว้ในสถานะปัจจุบันต้องมี **เพียงพอ** ที่จะใช้ตัดสินใจเลือกทางเดินต่อไปในอนาคตได้อย่างอิสระ โดยไม่ต้องย้อนกลับไปดูอดีตอีก .
"Dynamic Programming is recursion without repetition" .
• อย่าโฟกัสที่ตัวตาราง (Table) เพราะมันเป็นแค่โครงสร้างข้อมูลสำหรับจดจำค่า .
• หากสูตรความสัมพันธ์เวียนเกิด (Recurrence) ผิดพลาด การมีตารางที่สวยงามก็ไม่สามารถให้คำตอบที่ถูกต้องได้ .
เริ่มจากฟังก์ชัน Recursion แบบ Brute force หรือ Complete Search เพื่อให้เห็นโครงสร้างที่ถูกต้องของปัญหา .
ใส่ Memoization หรือเปลี่ยนเป็น Iterative เพื่อลดความซับซ้อนจากระดับ Exponential เหลือ Polynomial .
นี่คือการยืนยันว่าคำตอบที่ดีที่สุดของปัญหาใหญ่ถูกสร้างขึ้นจากคำตอบที่ดีที่สุดของปัญหาย่อยจริงๆ .
"หากเราตัดส่วนท้ายของคำตอบที่ดีที่สุดออก ส่วนที่เหลือต้องยังคงเป็นคำตอบที่ดีที่สุดสำหรับปัญหาย่อยที่สั้นลงนั้นด้วย" .
Divide & Conquer
แบ่งปัญหาเป็นส่วนย่อยที่ **แยกจากกัน** (Disjoint) และนำผลลัพธ์มาประกอบกัน .
Dynamic Programming
ใช้เมื่อปัญหาย่อยมีการ **ทับซ้อนกัน** (Overlapping) การจดจำค่าจึงช่วยลดงานซ้ำซ้อนได้อย่างมหาศาล .
คุณพร้อมสำหรับช่วงบ่ายแล้ว!
เราได้เรียนรู้วิธีการเปลี่ยนจาก Recursion ไปเป็นอัลกอริทึม DP ที่มีประสิทธิภาพ . ช่วงบ่ายเราจะนำความรู้นี้ไปใช้กับปัญหาคลาสสิก: **Coin Change, Knapsack และ LIS** .