418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 3

ให้ $OPT(i)\,$ คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้ง

ร้านจากตำแหน่งที่ 1 จนถึงตำแหน่งที่ $i\,$

ดังนั้นกรณีที่ $i=0\,$ จะได้ว่า $OPT(0)=0\,$

ส่วนกรณีที่ $i>0\,$ จะได้ว่า $OPT(i)=max(OPT(i-1),p_{i}+OPT(q_{i}))\,$ เมื่อ $q_{i}\,$ คือจำนวนเต็มที่มากที่สุดที่

ทำให้ $m_{i}-m_{q_{i}}>k\,$ นั่นคือการพิจารณาตำแหน่งที่ $i\,$ เราก็มีทางเลือกอยู่สองทางคือตั้งร้านหรือไม่ตั้งร้าน ถ้าไม่ตั้งร้าน ดังนั้นตำแหน่งที่

เราจะตั้งได้ก็ลดลงไปอีกหนึ่ง เหมือนกับไม่คิดถึงการตั้งร้านที่ตำแหน่งที่ $i\,$ นี้นี่เอง ส่วนถ้าเลือกการตั้งร้านที่ตำแหน่งที่ $i\,$ นี้ แน่นอน

เราได้กำไรรวมแล้ว $p_{i}\,$ หลังจากนั้นเราจะไม่สามารถตั้งร้านได้อีกภาย

ในระยะ $k\,$ จากร้านที่ตำแหน่งที่ $i\,$ นี้ ซึ่งในที่นี้เรา

ใช้ตัวแปร $q_{i}\,$ แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือ

ไม่เป็นตำแหน่งต่อไป

เขียนเป็น pseudocode ได้ดังนี้