💡 บทนำ: Dynamic Programming (DP) คืออะไร?
เคยไหม? ที่ต้องคิดเลขซ้ำๆ เรื่องเดิมๆ จนปวดหัว... คอมพิวเตอร์ก็เหมือนกันครับ! ถ้าเราเขียนโปรแกรมไม่ดี มันก็ต้องทำงานหนักฟรีๆ
หัวใจของ DP: "อย่าทำเรื่องเดิมซ้ำสอง" (Don't repeat yourself)
วิธีการแก้คือ เราจะใช้เทคนิคที่เรียกว่า Memoization (เมมโม-ไอ-เซชั่น) หรือแปลง่ายๆ ว่า "การจดบันทึก"
📝 เปรียบเทียบง่ายๆ:
เหมือนเวลาครูถามคำถามยากๆ ถ้าเราคิดคำตอบได้แล้ว เราก็ "จดใส่สมุด" ไว้
พอครูถามคำถามเดิมอีก เราก็แค่ "เปิดสมุดตอบ" ได้เลย ไม่ต้องคิดใหม่ให้เสียเวลา!
เหมือนเวลาครูถามคำถามยากๆ ถ้าเราคิดคำตอบได้แล้ว เราก็ "จดใส่สมุด" ไว้
พอครูถามคำถามเดิมอีก เราก็แค่ "เปิดสมุดตอบ" ได้เลย ไม่ต้องคิดใหม่ให้เสียเวลา!
🐰 บทที่ 1: Fibonacci Sequence
ลำดับตัวเลขมหัศจรรย์: 0, 1, 1, 2, 3, 5, 8, ...
กฎ: ตัวเลขตัวถัดไป = 2 ตัวหน้าบวกกัน
F(n) = F(n-1) + F(n-2)
💻 กิจกรรม: สมุดจดของ Fibonacci
ลองดูว่าถ้าเราใช้ "สมุดจด" (Memoization) คอมพิวเตอร์จะทำงานเร็วขึ้นแค่ไหน
กดปุ่มคำนวณเพื่อเริ่ม...
Waiting for command...
🏃 บทที่ 2: Climbing Stairs (ขึ้นบันได)
มีบันได N ขั้น เราก้าวได้ทีละ 1 ขั้น หรือ 2 ขั้น ถามว่ามีกี่วิธีที่จะขึ้นไปถึงชั้นบนสุด?
แนวคิด: การจะถึงขั้นที่ 5 ได้ เราต้องมาจากขั้นที่ 4 (ก้าว 1) หรือ ขั้นที่ 3 (ก้าว 2)
(เอ๊ะ! นี่มันสูตรเดียวกับ Fibonacci เลยนี่นา!)
วิธี(N) = วิธี(N-1) + วิธี(N-2) (เอ๊ะ! นี่มันสูตรเดียวกับ Fibonacci เลยนี่นา!)
Waiting for command...
🤖 บทที่ 3: Grid Traveler (หุ่นยนต์นักเดินทาง)
หุ่นยนต์ต้องการเดินจาก มุมซ้ายบน ไป มุมขวาล่าง โดยเดินได้แค่ ลง หรือ ขวา เท่านั้น
แนวคิด: จำนวนวิธีของช่องปัจจุบัน = (วิธีจากช่องด้านบน) + (วิธีจากช่องด้านซ้าย)
Waiting for command...