แนะนำ Dynamic programming แบบนิ่มนวลที่สุด
/ 3 min read
สามารถดู video ของหัวข้อนี้ก่อนได้ ดู video
Dynamic programming คืออะไร ?
Dynamic programming คือ เทคนิคหนึ่งที่ใช้สำหรับแก้ปัญหาที่ ปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) โดยการพยายามแก้ปัญหาย่อยก่อน แล้วค่อยมาสู่การแก้ปัญหาที่ใหญ่ขึ้น
ใน ครั้งนี้ผมจะหยิบ 2 เทคนิคนี้มาอธิบายคือ
- Memorization (Top-down approach) คือ ทำอะไรไว้ก็จำด้วย จะได้ไม่ต้องทำปัญหาย่อยซ้ำ เพื่อให้คิดวิธีแก้ปัญหาใหญ่ได้ไวขึ้น
- Tabulation (Bottom-up approach) คือ ทำจากอะไรเล็กๆก่อน (ที่เป็นคำตอบที่ดีที่สุดของปัญหานั้น) แล้วค่อยมารวมกันตอบปัญหาใหญ่อีกที
เริ่มต้นกับตัวอย่าง fibonacci
Recursive แบบปกติ
ปัญหาอยู่ที่
- ต้องพิจารณาทุกเคส
- เกิดเคสทำซ้ำเกิดขึ้น
ปัญหาของเรื่องนี้เราต้องวัดกันที่ Big O
Big O คือ complexity ของ algorithm ยิ่งเยอะ = ยิ่ง operation เยอะตาม
Ref: https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/
ถ้า list มาเฉพาะ Big O ที่เราจะได้วิเคราะห์จะเหลือเพียง
- O(1) = Constant (ไม่ว่าจะใส่อะไรเข้าไปก็ทำเพียงคำสั่งเดียว เช่น +, - เลข)
- O(log n) = เวลาลดลงครึ่งหนึ่งในทุกรอบที่ทำ
- O(n) = linear time = loop เดียว
- O(n^2) = 2 loop
- O(2^n) = เช็คใช่ไม่ใช่ทุกเคส
Fibo แบบ recursive = O(2^n)
DP Memorization - Top-down Dynamic Programming
- ทำอะไรไปแล้วก็จำ
- เช่น ถ้าเกิดว่า fibo(3) ถูกคิดไปแล้วจากตอน recursive ครั้งไหน = ให้เก็บไว้ใน memo[3]
- เพื่อที่ตอนที่วน recursive กลับมาจาก fibo(3) จากตัวอื่น จะได้สามารถเรียกใช้จาก memo[3] แทนที่จะต้องไปคำนวนใหม่
code ตัวอย่าง
DP Tabulation - Bottom-Up Dynamic Programming
- ทำจากเล็กๆแล้วไล่ไปจนถึงเป้าหมาย
- เช่นจากเคสนี้คือ เราจะเริ่มทำจาก fibo(1) -> fibo(2) … -> fibo(n) และนำ fibo(n) ที่เก็บใน array มาตอบแทน
code ตัวอย่าง
ตัวอย่างจากโจทย์ใน leet code
ที่ผมเลือกหยิบเป็น 2 ข้อนี้มา เพราะมี solution แปะไว้อยู่แล้วใน leetcode เช่นกัน อาจจะไม่ได้ใช้วิธีที่ผมใช้ซะทีเดียว แต่สามารถนำไปเรียนรู้ประกอบได้
- โจทย์ Memorization Word Break https://leetcode.com/problems/word-break
Note
- ถ้าทำแบบปกติทั่วไป จะต้องเช็ค เอา / ไม่เอา = ใช้ O(2^n)
- ถ้าทำแบบ DP คือ
- เราจะจำตำแหน่งก่อนหน้าว่าตัดสำเร็จหรือไม่ = ถ้าสำเร็จให้บอกตำแหน่งถัดไปเพื่อบอกว่า ก่อนหน้านี้เราตัดสำเร็จแล้ว
- เพื่อที่จะได้ไม่ต้องวนเช็คทุก combination ได้
- Big O จะเหลือเพียง O(n^2) โดย n คือขนาดของ string s แทน
code solution ของ ข้อนี้
Solution
- เก็บ memo เอาไว้ว่าแต่ละ index เคยเจอไหม
- ถ้าปลายเจอ = จำไว้ว่าสามารถเจอคำนี้ได้
- ส่งคำตอบเป็นตำแหน่งสุดท้ายของ array ไปว่ายังคงตัดคำได้ไหม
- ตัวอย่าง Tabulation Generate Parentheses https://leetcode.com/problems/generate-parentheses/
Note
- ถ้าทำแบบปกติทั่วไป ต้องเช็คทุกเคสว่า วางวงเล็บ / ไม่วางวงเล็บ = เช็คว่าเอา / ไม่เอา = O(2^n)
- ถ้าทำแบบ DP
- เราจะเริ่มทำจาก () ที่สำเร็จก่อนที่ n = 1
- หลังจากนั้นเราจะค่อยๆประกอบ () มาจาก assamption ที่ว่า วงเล็บจะยังคงเป็นวงเล็บที่ถูกต้องเสมอ ถ้าเราเอา () อะไรก็ตามมาวางไว้ตรงกลาง หรือ ด้านข้าง แบบนี้
(_)_
- เช่น n = 2 จะต้องมี () ทั้งหมด 2 อัน เราก็จะทำ () ไปแทนที่ตำแหน่ง _ ในแต่ละเคสโดย
()()
เมื่อ _ แรก = ” และ _ ที่สอง = (),(())
เมื่อ _ แรก = () และ _ ที่สอง = () - Big O จะเหลือเพียงราวๆ O(n^2) ได้โดย n คือจำนวนวงเล็บที่ต้องการ
code solution ของข้อนี้
Solution
- เริ่มทำจาก 1 วงเล็บ, 2 วงเล็บ จนถึง n วงเล็บ
- ทุกๆการประกอบวงเล็บเราจะวนกลับไปใช้วงเล็บเดิมมาประกอบ เช่น 3 วงเล็บเกิดจาก 0 วงเล็บ + 2 วงเล็บ, 1 วงเล็บ + 1 วงเล็บ (ที่มาของ loop i, j)
- คำตอบจะอยู่กับตำแหน่ง array สุดท้าย (ตำแหน่งที่ n)
Note ส่งท้าย
นี่ยังเป็นเพียงเรื่องเล็กๆของ Dynamic Programming จริงๆ มันยังมีเนื้อหาและโจทย์น่าสนใจให้ลองทำดู
- ยังมีปัญหาท้าทายใน Dynamic Programming อีกมากเช่น
- Knapsacks
- Longest common subsequence (LCS)
- Longest Increasing Subsequence
- Maximum Subarray Sum
หาอ่านเพิ่มเติมกันได้ที่
- https://www.geeksforgeeks.org/dynamic-programming/
- https://medium.com/@aquablitz11/an-introduction-to-dynamic-programming-76574fda6501
- Random บน Computer สุ่มแบบไหนเราถึงเรียกว่าสุ่ม ?มี Video
เคยสงสัยกันไหมครับ เวลาที่เราทอยลูกเต๋า สุ่มหยิบการ์ดออกจากกอง หรือแม้แต่สุ่มโดยการทอยเหรียญ สิ่งนี้เมื่อย้ายเข้าไปทำงานอยู่บนคอมพิวเตอร์มันทำงานยังไง
- มาลองเล่น Gemini Pro กันมี Video มี Github
มาทำความรู้จักกับ Gemini Pro และ Prompt design กันว่าเราสามารถเอา Gemini ไปทำอะไรได้บ้าง
- รู้จักรูปแบบ Authentication ระหว่าง Frontend และ Backendมี Video มี Github
เราจะพามาทำ Authentication กับการ Login กัน ว่ามีกี่วิธีที่สามารถทำได้ และสามารถทำได้ยังไงกันบ้าง ซึ่งจะพาทำกันตั้งแต่ฝั่งของ API Backend
- มาเรียนรู้การทำ Frontend Testing ผ่าน React กันมี Video
แนะนำพื้นฐานการทำ Component Testing สำหรับการทำ Unit testing ฝั่ง Frontend