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

ให้ $OPT(i)\,$ เป็น penalty ที่น้อยที่สุดที่พิจารณาการเดินทางจากตำแหน่งที่ $i\,$ ถึงตำแหน่งที่ $n\,$

พิจารณากรณีที่ $i=n\,$ จะได้ว่า $OPT(n)=0\,$

กรณีที่ $i<n\,$ จะได้ว่า $OPT(i)=min_{(i+1)\leq j\leq n}((200-(a_{j}-a_{i}))^{2}+OPT(j))\,$

คือถ้าพิจารณาการเดินทางที่มาหยุดที่ตำแหน่งที่ $i\,$ ใด ๆ ที่ไม่ใช่ตำแหน่งสุดท้ายแล้ว การตัดสินใจต่อไปคือจะไปหยุดที่ตำแหน่งไหนเป็นตำแหน่งต่อไป ซึ่งตำแหน่งที่เราสามารถหยุดได้คือ ตำแหน่งที่ $a_{j}\,$ โดยที่ $(i+1)\leq j\leq n\,$ นั่นเอง แล้วเราต้องเลือกหยุดตำแหน่งที่ทำให้ penalty น้อยที่สุดด้วย

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

<geshi lang="c"> TRAVEL(a,n)

   M[n] = 0
   for i = 1 to n do
       min = infinity
       for j = i+1 to n do
           if (200-(a[j]-a[i]))^2 + M[j] < min then
               min = (200-(a[j]-a[i]))^2 + M[j]
       M[i] = min
   return M[0] // ส่ง ค่า M[0] เป็นคำตอบที่เป็น penalty ที่น้อยที่สุดที่พิจารณาการเดินทางจากตำแหน่ง 0 ไป n เป็นคำตอบ   

</geshi>