Introduction

“1+1+1+1+1+1+1+1 = ?”

จากโจทย์ด้านบนเชื่อว่าทุกคนก็คงจะตอบว่า 8 ใช่ไหมหละครับ (จากการนับเลข 1 เอาว่ามีกี่ตัว) …ถ้าเราถามต่อไปว่า “แล้วเราถ้าเขียน 1+ เพิ่มทางด้านซ้าย” คำตอบจะกลายเป็นเท่าไหร่?

“เก้า!” เราเชื่อว่าทุกคนก็คงจะสามารถคำนวนหาคำตอบออกมาได้เลยในทันทีโดยไม่ต้องเสียเวลามานั่งนับเลขหนึ่งใหม่ เพราะเรา “จำ” ได้อยู่แล้วว่าคำตอบก่อนหน้านี้คือ 8 ดังนั้นถ้าเพิ่ม 1+ เข้ามาก็ต้องกลายเป็น 9 นั่นเอง

Dynamic programming is just a fancy way to say “remembering stuff to save time later.” Jonathan Paulson, Quora

คำอธิบายข้างต้นเป็นตัวอย่างที่เรายกมาจากคำถามใน Quora ที่มีคนมาโพสถามว่า “How should I explain dynamic programming to a 4-year-old?” ซึ่งเป็นคำอธิบายที่เรามองว่าน่าสนใจมากเพราะสั้น กระชับ และได้ใจความ

หรืออีกตัวอย่างหนึ่งที่เราเชื่อว่าถ้าใครหัดเขียนโปรแกรมมาต้องเคยผ่าานตากันมาบ้างอยู่แล้วก็คือ Fibonacci sequence ที่ตัวเลข ณ ตำแหน่งใดตำแหน่งหนึ่งจะเกิดจากตัวเลข 2 ตัวในตำแหน่งก่อนหน้าบวกกัน

“0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …”

แน่นอนว่าเพื่อหา fibonacci number ในตำแหน่งที่ \(n\) เราสามารถที่จะเขียน recursive function ออกมาได้ จากนั้นทำการ “จำ” เพื่อลดการคำนวนที่ซ้ำซ้อนลงเพื่อให้สามารถคำนวนได้ไวขึ้น

(สามารถลองค้นดูในเน็ตได้เลยมีตัวอย่างเยอะมาก; หรืออาจจะลองดูคลิปของพี่ไท “Dynamic programming in a nutshell” — โดยเฉพาะนาทีแรกถึงนาทีที่ 7:40)

“Dynamic programming คือ recursive + cache” Thai Pangsakulyanont

จากตัวอย่างข้างต้นจะเห็นได้ว่าการ “จำคำตอบที่เราเคยคำนวนไว้แล้ว จะได้ไม่ต้องคำนวนอีก” จะเป็นหัวใจสำคัญของ dynamic programming; แต่อย่างไรก็ตามเราก็จะมีคำถามต่อไปอีกว่า

  • “ปัญหาต้องมีลักษณะแบบไหนจึงเหมาะกับการจำ?”
  • “เราสามารถแก้ปัญหาที่มีลักษณะดังกล่าวด้วยวิธีการไหนได้บ้าง?” (implementation)
  • “แล้วเราจะรู้ว่าได้อย่างไรว่าปัญหาไหนใช้ dynamic programming แก้ได้? อะไรคือข้อสังเกต (หรือ clue) ที่เราสามารถสังเกตมันได้?”

ในบทความนี้จะชวนทุกคนมาหาคำตอบของคำถามเหล่านี้และมาทำความเข้าใจกับ dynamic programming ให้ลึกมากขึ้นกันครับ

เมื่อปัญหาเดียวกันทับซ้อนกัน

ก่อนที่เราจะไปคุยกันที่นิยามของ dynamic programming นั้นเราอยากจะพาทุกคนกลับมาทำความเข้าใจ fibonacci sequence ให้เห็นภาพมากขึ้นอีกสักหน่อย

โดยถ้าหากว่าเราให้ function \(f(n)\) แทน fibonacci number ตำแหน่งที่ \(n\) เราก็สามารถที่จะเขียน recursive case และ base case ของ function ดังกล่าวออกมาได้ว่า

f(n)=f(n1)+f(n2) f(0)=0f(1)=1f(n) = f(n-1) + f(n-2)\\ \text{ } \\ f(0) = 0 \\ f(1) = 1

เราจะเห็นว่า\(f(n)\) นั้นจะประกอบไปด้วย 2 “ปัญหาเดียวกันที่เล็กกว่า” (หรือเรียกว่า “sub-problem”) ด้านในซึ่งได้แก่ \(f(n - 1)\) และ \(f(n - 2)\)

ถ้าสมมุติว่าเราแก้ปัญหา \(f(4)\) เราสามารถที่จะเขียน relationship ของ sub-problem ต่าง ๆ ออกมาได้โดยใช้ tree ; ซึ่งสามารถเขียนออกมาได้ดังนี้

Fibonacci Tree
ให้ vertex แทน “sub-problem” (สีของ vertex ที่เหมือนกันคือ problem เดียวกัน)

จากภาพจะเห็นได้ว่ามีการแก้ปัญหาที่ซ้ำซ้อนกันเยอะมาก เราต้องคำนวน \(f(2)\) ตั้งสองครั้ง ทั้ง ๆ ที่มันเป็นปัญหาเดียวกัน ดังนั้นจะดีกว่าไหมถ้าหากว่าเราไม่ต้องคำนวนปัญหาเดิม ๆ ซ้ำ ๆ?

จากตรงนี้เราสามารถลากเส้นของ tree ดังกล่าวใหม่ได้ครับ แทนที่จะแตก sub-problem ใหม่ออกมาเป็น tree; ถ้าหากว่ามี sub-problem ใด ๆ อยู่แล้ว เราจะไม่สร้าง sub-problem ใหม่ แต่โยงลูกศรไปที่ sub-problem นั้นแทน

Fibonacci DAG
ให้ vertex แทน “sub-problem” และ edge แทนว่า vertex ไหนต้องทำ vertex ไหนให้เสร็จก่อนถึงจะทำ vertex นั้นได้

\(f(4)\) โยงไปที่ \(f(3)\) และ \(f(2)\); \(f(3)\) โยงไปที่ \(f(2)\) และ \(f(1)\); \(f(2)\) โยงไปที่ \(f(1)\) และ \(f(0)\)

จะเห็นว่าจาก tree ที่มี sub-problem เดียวกันซ้ำกันเยอะมาก ตอนนี้กลายเป็น graph ที่ไม่มี sub-problem ไหนซ้ำกันอีกแล้ว จากเดิมที่เรามี sub-problem มากถึง \(2^n\) ตอนนี้เราเหลือ sub-problem เพียงแค่ \(n\) ตัวเท่านั้น — \(O(n)\)

เราเรียกปัญหาที่มี sub-problem ซ้ำ ๆ กันว่า “overlapping sub-problems” ครับ และเมื่อมี overlapping sub-problems เราจึงสามารถ reuse sub-problem และลดรูปจาก tree ให้กลายเป็น graph ข้างต้นได้

Overlapping sub-problem เป็นหนึ่งใน attribute สำคัญของปัญหาที่สามารถใช้ dynamic programming แก้ได้ เพราะเมื่อมีปัญหามันซ้ำกัน เราจึงสามารถที่จะจำมันไว้และไม่ต้องคำนวนมันใหม่ได้นั่นเอง

(ปัญหาที่ไม่มี overlapping sub-problem อย่างเช่น binary search หรือ merge sort เราจะเรียกมันว่า “divide and conquer algorithm” แทน)

เรามักเรียก graph ที่ลดรูปมาจาก tree ดังกล่าวว่า DAG หรือ “directed acyclic graph” ครับ โดยปัญหาที่แก้ได้โดย dynamic programming สามารถที่จะเขียนออกมาเป็น DAG ได้หมดเลย ซึ่งหลังจากนั้นเราก็สามารถใช้ algorithm ในการหาได้ว่า sub-problem ไหนควรจะต้องถูกแก้ก่อนหรือหลัง และสามารถคำนวนหาคำตอบของปัญหาใหญ่ออกมาได้ในที่สุด

Implementation

ตอนนี้ทุกคนเห็นแล้วว่าเราสามารถที่จะไม่ต้องคำนวน overlapping sub-problem ซ้ำ ๆ ได้ คราวนี้มาดู in action กันบ้างครับว่าเราสามารถที่จะ implement มันออกมาในรูปแบบไหนได้บ้าง

Recursive Function + Memorization

วิธีการแรกคือการที่เราสามารถเขียน recursive function แบบตรงไปตรงมาออกมาได้เลย จากนั้นเราจะทำการ “จำ” ครับว่า เช่นถ้าหากว่าเราเคยคำนวน \(f(2)\) ไปแล้ว เราก็จะจำคำตอบนั้นไว้และ return คำตอบดังกล่าวออกไปเลยแทนที่จะต้องมาคำนวนใหม่

เราเรียกการจำดังกล่าวว่า “memorization” ครับ ซึ่งเป็นเทคนิคในการทำ cache แบบหนึ่ง

โดยเราสามารถเขียนโค้ดออกมาได้ดังนี้เลย

1
function fibonacci(n, memo = {}) {
2
// Base cases
3
if (n == 0) return 0;
4
if (n == 1) return 1;
5
6
// Check if the result is already memoized
7
if (memo[n] !== undefined) {
8
return memo[n];
9
}
10
11
// Calculate and memoize the result
12
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
13
14
return memo[n];
15
}

Time complexity: \(O(n)\); Space complexity: \(O(n)\)

Tabulation

อย่างไรก็ตามจะเห็นว่าจากวิธีการก่อนหน้านี้เราต้องสร้าง memo ขึ้นมาเพื่อจำคำตอบของ sub-problem แต่ละตัวใช่ไหมครับ ซึ่งจะใช้ space complexity \(O(n)\)

ทั้งนี้เราสามารถที่จะลด space complexity ลงได้โดยการจำข้อมูลเท่าที่จำเป็นเท่านั้นครับ; ก่อนอื่นทุกคนยังจำรูปของ graph ที่เราสร้างขึ้นมาได้ไหมครับ

Fibonacci DAG

ถ้าหากว่าเราลองหา order ของการคำนวนเราจะพบว่า เราต้องคำนวน \(f(0)\) และ \(f(1)\) ก่อน \(f(2)\); \(f(1)\) และ \(f(2)\) ก่อน \(f(3)\); \(f(2)\) และ \(f(3)\) ก่อน \(f(4)\)

จากตรงนี้เองเราสามารถสร้างตัวแปรขึ้นมาสองตัว a และ b เพื่อใช้ในการเก็บค่า sub-problem สองตัวก่อนหน้า

1
function fibonacci(n) {
2
// Base cases
3
if (n == 0) return 0;
4
if (n == 1) return 1;
5
6
// Initialize two variables to store the last two Fibonacci numbers
7
let a = 0;
8
let b = 1;
9
10
// Calculate Fibonacci numbers iteratively
11
for (let i = 2; i <= n; i++) {
12
const n = a + b;
13
a = b;
14
b = n;
15
}
16
17
// Return the nth Fibonacci number
18
return b;
19
}

Time complexity: \(O(n)\); Space complexity: \(O(1)\)

อย่างไรก็ตามสำหรับ tabulation เราสามารถเลือกที่จะไม่ต้อง save space complexity ได้เช่นกันโดยการสร้าง table ที่ชื่อว่า dp ขึ้นมาโดยให้ dp[n] เก็บคำตอบของ fibonacci number ตำแหน่งที่ n โดยเราสามารถเขียนโค้ดออกมาได้ดังนี้

1
function fibonacci(n) {
2
// Initialize the dp array with 0s
3
const dp = new Array(n + 1).fill(0);
4
5
// Set the first two fibonacci numbers
6
dp[0] = 0;
7
dp[1] = 1;
8
9
// Fill up the dp array
10
for (let i = 2; i <= n; i++) {
11
dp[i] = dp[i-1] + dp[i-2];
12
}
13
14
// Return the nth fibonacci number
15
return dp[n];
16
}

Time complexity: \(O(n)\); Space complexity: \(O(n)\)

Key หลักของ tabulation คือการที่เราสร้าง table ขึ้นมาจากนั้นค่อย ๆ fill up table ดังกล่าวจากปัญหาที่เล็กที่สุดไปหาปัญหาที่ใหญ่ที่เราต้องการจะแก้

เรามักเรียกวิธีการ recursive + memorization ว่า “top-down” ครับเพราะเริ่มจากการ define ปัญหาในภาพใหญ่ และปล่อยให้ recursive function แก้ปัญหาที่เล็กลงไปเรื่อย ๆ ในขณะที่เรามักเรียกวิธีการ tabulation ว่า “bottom-up” เนื่องจากเราจะเริ่มแก้ปัญหาที่เล็กที่สุดก่อน จากนั้นค่อย ๆ construct ปัญหาที่ใหญ่ขึ้นไปเรื่อย ๆ จนสามารถแก้ปัญหาใหญ่ได้ในที่สุด

เมื่อคำตอบของปัญหาย่อยนำไปสู่คำตอบของปัญหาใหญ่

อย่างไรก็ตาม การที่เราจะแก้ปัญหาด้วย dynamic programming ได้นั้นเราจะต้องมองเห็น overlapping sub-problem หรือ “ปัญหาเดียวกันที่ทับซ้อนกันอยู่” เสียก่อน ซึ่งการจะมองให้เห็นสิ่งนี้เรามองว่ามันเป็น “art” หรือ skill ที่ต้องฝึกที่จะมอง

เราเคยอธิบายไว้ในบท recursion ว่าเราจะเห็น recursive pattern หรือไม่นั้นมันข้ออยู่กับว่าเรา “กำหนดนิยามของสิ่ง ๆ หนึ่งขึ้นมาอย่างไร” ในแบบที่มันมี ‘สิ่ง ๆ หนึ่งที่หน้าตาเหมือนกัน’ อยู่ในนั้น เหมือนกับกระจกสองใบที่เมื่อวางในองศาที่ถูกต้องเราก็จะเห็นภาพซ้อนที่ไม่รู้จบเกิดขึ้นมา

แต่ถึงอย่างนั้นไม่ใช่ว่าเราจะต้องลองผิดลองถูกจนกว่าจะเจอนิยามที่ถูกต้องครับ เรามีตัวช่วย! และเราสามารถเห็นตัวช่วยที่ว่านั้นผ่านการสังเกตปัญหาอย่าง fibonacci ที่เราพึ่งจะแก้ไปครับ

Optimal Substructure

จากภาพเราจะเห็นว่าคำตอบของ \(f(4)\) นั้นเกิดจากนำคำตอบของ \(f(3)\) และ \(f(2)\) “มาคำนวนด้วยวิธีการบางอย่าง”

ซึ่งเราเรียก “การเรานำคำตอบของปัญหาย่อยมาคำนวนด้วยวิธีการบางอย่างเพื่อหาคำตอบของปัญหาที่ใหญ่ขึ้น” แบบนี้ว่า “optimal substructure” ครับ ซึ่งเป็นอีกหนึ่ง attribute สำคัญของปัญหาที่สามารถใช้ dynamic programming แก้ได้

มันนำมาสู่คำถาม (และเป็นตัวช่วยสำคัญ) ที่ว่า

จากนิยามปัญหาของเรา “ถ้าหากเรารู้คำตอบของปัญหาย่อย เราสามารถใช้มันในการหาคำตอบของปัญหาที่ใหญ่ขึ้นได้หรือไม่?”

เพื่อให้เห็นภาพเราลองมาแก้ปัญหาง่าย ๆ ไปด้วยกันดูครับ

ปล้นให้ได้มากที่สุด

(สามารถลองทำโจทย์ก่อนได้ที่ LeetCode “198. House Robber”)

สมมุติว่าคุณเป็นโจรมืออาชีพที่ออกปล้นบ้านตอนกลางคืน โดยกำหนดให้มีบ้านติดกัน n หลัง แต่ละหลังมีมูลค่าที่สามารถปล้นได้แตกต่างกัน กฏข้อเดียวก็คือ “ห้ามปล้นบ้านที่อยู่ติดกัน” คำถามก็คือ “มูลค่าสูงสุดที่คุณสามารถปล้นได้มีค่าเท่าไหร่?”

House Robber Example

ก่อนอื่นถ้าเรามาลองกำหนดนิยามของ function กันเล่น ๆ โดยกำหนดให้ \(f(i)\) แทน “มูลค่าสูงสุดที่สามารถปล้นได้ตั้งแต่ index 0 ถึง i” เราอาจจะลองถามต่อไปว่า จากนิยามปัญหาของเรา “ถ้าหากเรารู้คำตอบของปัญหาย่อย เราสามารถใช้มันในการหาคำตอบของปัญหาที่ใหญ่ขึ้นได้หรือไม่?”

ถ้าหากเราลองพยายามหาคำตอบดูเราก็จะพบว่าคำตอบก็คือ “ไม่” เพราะสมมุติว่าเรารู้ \(f(i-1)\) เราจะเอาคำตอบมารวมกับ \(nums[i]\) ไม่ได้ เพราะเราไม่รู้ว่าคำตอบของ \(f(i-1)\) นั้นรวมบ้านหลังที่ \(i - 1\) ด้วยหรือไม่ (ซึ่งถ้ารวมก็จะผิดโจทย์เพราะห้ามปล้นบ้านหลังติดกัน)

จะเห็นว่าการรู้ว่ารวมบ้านหลังที่ \(i\) หรือไม่นั้นเป็นเรื่องที่สำคัญมาก ดังนั้นเราอาจจะลองเปลี่ยนนิยาม…

  • กำหนดให้ \(\text{f_include}(i)\) แทน “มูลค่าสูงสุดที่สามารถปล้นได้ตั้งแต่ index 0 ถึง i; โดยต้องมีบ้านหลังที่ i อยู่ในคำตอบด้วย”
  • และ \(\text{f_not_include}(i)\) แทน “มูลค่าสูงสุดที่สามารถปล้นได้ตั้งแต่ index 0 ถึง i; โดยห้ามมีบ้านหลังที่ i อยู่ในคำตอบ”

จากนิยามปัญหาของเรา “ถ้าหากเรารู้คำตอบของปัญหาย่อย เราสามารถใช้มันในการหาคำตอบของปัญหาที่ใหญ่ขึ้นได้หรือไม่?”

คำตอบก็คือได้ครับ โดยในเคสของ \(\text{f_include}(i)\) (ลองค่อย ๆ ไล่นิยามไปด้วยกันนะครับ)

  • ถ้าหากว่าเรารู้ \(\text{f_include}(i-2)\) เราก็สามารถคำนวนค่า \(\text{f_include}(i)\) ได้จาก \(\text{f_include}(i-2) + nums[i]\)
  • ถ้าหากว่าเรารู้ \(\text{f_not_include}(i-1)\) เราก็สามารถคำนวนค่า \(\text{f_include}(i)\) ได้จาก \(\text{f_not_include}(i-1) + nums[i]\)

ดังนั้นโดยสรุปแล้ว

f_include(i)=max{f_include(i2)+nums[i],f_not_include(i1)+nums[i]} f_include(0)=nums[0]\text{f\_include}(i) = max\{ \text{f\_include}(i-2) + nums[i], \text{f\_not\_include}(i-1) + nums[i] \} \\ \text{ } \\ \text{f\_include}(0) = nums[0]

และในเคสของ \(\text{f_not_include}(i)\)

  • ถ้าหากว่าเรารู้ \(\text{f_include}(i-1)\) เราก็ใช้เป็นคำตอบของ \(\text{f_not_include}(i)\) ได้เลย
  • ถ้าหากว่าเรารู้ \(\text{f_not_include}(i-1)\) เราก็ใช้เป็นคำตอบของ \(\text{f_not_include}(i)\) ได้เลยอีกเช่นกัน

ดังนั้นโดยสรุปแล้ว

f_not_include(i)=max{f_include(i1),f_not_include(i1)} f_not_include(0)=0\text{f\_not\_include}(i) = max\{ \text{f\_include}(i - 1), \text{f\_not\_include}(i-1) \} \\ \text{ } \\ \text{f\_not\_include}(0) = 0

ดังนั้นคำตอบของปัญหาหลักของเราก็คือค่า max ระหว่าง \(\text{f_include}(n - 1)\) และ \(\text{f_not_include}(n - 1)\) นั่นเอง

rob(n)=max{f_include(n1),f_not_include(n1)}\text{rob}(n) = max\{ \text{f\_include}(n-1), \text{f\_not\_include}(n-1) \}

เขียนโค้ดแบบ recursive function + memorization ⤵

1
function rob(nums) {
2
const n = nums.length;
3
const memo_include = new Array(n).fill(-1);
4
const memo_not_include = new Array(n).fill(-1);
5
6
function f_include(i) {
10 collapsed lines
7
// Base case
8
if (i === 0) return nums[0];
9
if (i < 0) return 0;
10
if (memo_include[i] !== -1) return memo_include[i];
11
12
memo_include[i] = Math.max(
13
f_include(i - 2) + nums[i],
14
f_not_include(i - 1) + nums[i],
15
);
16
return memo_include[i];
17
}
18
19
function f_not_include(i) {
7 collapsed lines
20
// Base case
21
if (i === 0) return 0;
22
if (i < 0) return 0;
23
if (memo_not_include[i] !== -1) return memo_not_include[i];
24
25
memo_not_include[i] = Math.max(f_include(i - 1), f_not_include(i - 1));
26
return memo_not_include[i];
27
}
28
29
return Math.max(f_include(n - 1), f_not_include(n - 1));
30
}

เขียนโค้ดแบบ tabulation ⤵

1
function rob(nums) {
2
const n = nums.length;
3
4
let dp_include = [];
5
let dp_not_include = [];
6
7
// Base cases
8
dp_include[0] = nums[0];
9
dp_not_include[0] = 0;
10
11
for (let i = 1; i < nums.length; ++i) {
12
// Recursive case: f_include
13
dp_include[i] = Math.max(
14
dp_include[i - 2] || 0 + nums[i],
15
dp_not_include[i - 1] + nums[i],
16
);
17
18
// Recursive case: f_not_include
19
dp_not_include[i] = Math.max(
20
dp_include[i - 1],
21
dp_not_include[i - 1]
22
);
23
}
24
25
return Math.max(dp_include[n - 1], dp_not_include[n - 1]);
26
}

Time complexity: \(O(n)\); Space complexity: \(O(n)\);

แล้ว Dynamic Programming คืออะไร?

สำหรับเราแล้ว dynamic programming มันคือวิธีการทั้งหมดที่เราแก้ปัญหาข้างต้นเลย

มันคือการ breakdown ปัญหาใหญ่ให้กลายเป็นปัญหาย่อย ๆ ที่มี overlapping sub-problem และ optimal substructure จากนั้นให้เทคนิคอย่าง memorization และ tabulation เพื่อลดการคำนวนที่ซ้ำซ้อนเพื่อให้แก้ปัญหาได้ไวขึ้น

จากนิยามข้างต้นนี้เอง เราสามารถสรุป problem-solving process สำหรับ dynamic programming ออกมาได้ดังนี้

  1. นิยามปัญหา หรือ function ให้ชัดเจนว่ารับค่าอะไรและ return ค่าอะไร
  2. จากนิยามปัญหาของเรา “ถ้าหากเรารู้คำตอบของปัญหาย่อย เราสามารถใช้มันในการหาคำตอบของปัญหาที่ใหญ่ขึ้นได้หรือไม่?” (ถ้าคำตอบคือไม่ ให้กลับไปทำข้อ 1)
  3. เขียน recursive case และ base case ของ function ดังกล่าวออกมา
  4. ปัญหาของเรามี overlapping sub-problem หรือไม่? ถ้ามีให้เลือกทำ memorization หรือ tabulation เพื่อลดการคำนวนที่ซับซ้อน

สุดท้ายนี้ก็คิดว่าทุกคนจะเข้าใจ dynamic programming มากขึ้นนะครับ ดังนั้นเราไปลุย review questions โจทย์ challenge problem วันนี้กันเลยดีกว่าครับ!

Challenge Problem

Coming Soon…