Catalan number (dynamic programming)
May 28, 2021
ลำดับ catalan สามารถหาได้ด้วยสูตร
โอเค ข้อนี้ค่อนข้างตรงไปตรงมา … มาลองทำกันดูเลยดีกว่า
- Naive way
ซึ่งวิธี recusive แบบนี้ ก็มักจะเจอปัญหา overlap subproblem ยกตัวอย่างง่ายๆ เช่น ตอนเราคิด catalan(5) เราก็ต้องคิด catalan(2) ไปด้วย … ตอนเราคิด catalan(6) เราก็ต้องมาคิด catalan(2) อีก
เราจะแก้ปัญหานี้ด้วยการ memorize ค่าไว้ แบบนี้
2. dynamic programming
Time complexity = O(n²) … โอเค ข้อนี้ก็จะประมาณนี้ ( มีวิธีอื่นอีก ลองไปดูกันได้ ตามลิงก์ )
