Dynamic Programming หรือย่อว่า DP คือแบบแผนของการเขียนอัลกอริทึมที่แบ่งปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ และเก็บคำตอบของปัญหาเหล่านั้นไว้เพื่อป้องกันการคำนวนสิ่งเดิมซ้ำอีก

ในตอนนี้เราจะพูดถึงการแก้ปัญหาที่มี Overlapping Subproblem ซึ่งเป็นปัญหาที่ตรงกับนิยามที่ให้ไปข้างบนเลย คือมีการคำนวนที่ซ้ำซ้อน  ตัวอย่างคลาสสิกของ DP คือเรื่องของการหาลำดับ Fibonacci (คิดว่าทุกคนคงรู้จัก Fibonacci อยู่แล้ว) นั้นคือลำดับที่เกิดจากการบวกกันของสองตัวก่อนหน้า

0, 1, 1, 2, 3, 5, 8, 13, ...
(ในทางคอมพิวเตอร์จะเพิ่ม 0 ขึ้นมาเป็นตัวแรก)

เราสามารถเขียนโปรแกรมหาเลข Fibonacci ในลำดับต่าง ๆ ได้ด้วยฟังก์ชัน Recurrsive ง่าย ๆ ดังนี้

int fibonacci(int n) {
	if(n==0 || n==1)
	 	return n;
	return fibonacci(n-1)+fibonacci(n-2);
}

ฟังก์ชันนี้ทำงานได้นะ เว้นเสียแต่พอค่า n เริ่มมากขึ้น เอาสัก 40 กว่าก็พอ เราจะสังเกตุได้เลยว่าโปรแกรมทำงานช้ามาก ทำไม? มาดูกัน  สมมุติเราเรียก fibonacci(6) สิ่งที่โปรแกรมนี้เรียกใช้คือ

สังเหตุว่าฟังก์ชันจะถูกเรียกขึ้นทีละสองครั้ง ๆ ดังนั้นจะมี O(2^n) แน่นอนว่ามันห่วยบรม

ด้วยหลัักของ DP คือเราจะเก็บคำตอบของปัญหาย่อย ๆ เอาไวัเพื่อที่จะได้ไม่ต้องคำนวนใหม่ ซึ่งในนี้ก็มีฟังก์ชันที่ถูกเรียกใช้หลายครั้งอยู่เต็มไปหมด งั้นเราลองแก้ไขปัญหานี้กัน โดยเราจะเก็บค่าของ fibonacci(n) ไว้ในอาเรย์ val ตำแหน่งที่ n และจะส่งค่า val[n] กลับไป

int fibonacci(int n) {
	static int val[50] = {};
	if(n==0 || n==1)
	 	val[n] = n;
	else if(val[n] == 0)
		val[n] = fibonacci(n-1)+fibonacci(n-2);
	return val[n];
}

(ที่กำหนดขนาดแค่ 50 เพราะแค่นี้ก็เกิน int ธรรมดาแล้ว)

พอเป็นแบบนี้แล้ว อัลกอของเราจะเหลือเพียง O(n) เท่านั้น วิธีนี้เรียกว่า Memoization ซึ่งเป็นการแก้ปัญหาแบบ Top-Down คือทำจากข้างหน้าลงไป ซึ่งเราก็มีวิธีอีกวิธีหนึ่ง คือแบบ Tabulation หรือ Bottom-Up เริ่มทำจากส่วนท้ายของปัญหาก่อน คือเรารู้ว่าสุดท้ายแล้วมันจะมาจบที่ fibonacci(0) = 0 และ fibonacci(1) = 1 ดังนั้นเราจะเริ่มทำจากตรงนี้

int fibonacci(int n) {
	int val[50];
	val[0] = 0; 
	val[1] = 1;
	for (int i = 2; i <= n; i++)
		val[i] = val[i-1]+val[i-2];
	return val[n];
}

ซึ่งทั้งสองวิธีต่างก็จำคำตอบย่อยทั้งสิ้น และทำงานในเวลาที่ใกล้เคียงกัน แต่ Tabulation จะมีข้อได้เปรียบตรงที่ในวีธี memoization เมื่อจำนวน stack ของการ recursive มีมาก ๆ แล้วบางทีจะเกิด error ขึ้นได้  แต่สำหรับ tabulation จะมีเยอะเพียงใดก็ได้ตราบที่ตัวแปรที่ใช้ลูปเก็บไหว

ในตอนต่อไปเราจะพูดถึงเรื่องของ Optimal Substructure ซึ่งเป็นปัญหาอีกรูปแบบหนึ่งที่การทำ DP จะมีประโยชน์อย่างมาก

ติดตามต่อใน  Basic DP II : Optimal Substructure
อ้างอิงจาก https://www.geeksforgeeks.org/dynamic-programming-set-1/