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

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

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

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

คือถ้าพิจารณาการเดินทางที่มาหยุดที่ตำแหน่งที่ <math> i \,</math> ใด ๆ ที่ไม่ใช่ตำแหน่งสุดท้ายแล้ว การตัดสินใจต่อไปคือจะไปหยุดที่ตำแหน่งไหนเป็นตำแหน่งต่อไป ซึ่งตำแหน่งที่เราสามารถหยุดได้คือ ตำแหน่งที่ <math> a_j \,</math> โดยที่ <math> (i+1) \leq j \leq n \,</math> นั่นเอง แล้วเราต้องเลือกหยุดตำแหน่งที่ทำให้ 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>