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

ให้ $OPT(i)\,$ มีค่าเป็น $yes\,$ ถ้าตัวอักษรที่ $1...i\,$ สามารถตัดคำได้ หรือมีค่าเป็น $no\,$ ถ้าตัวอักษรที่ $1...i\,$ ไม่สามารถตัดคำได้

การที่ตัวอักษรตัวที่ $1...i\,$ สามารถตัดคำได้นั้น หมายความว่า สตริงที่ประกอบด้วยตัวอักษรตัวที่ $1...i\,$ นั้นต้องมีคำสุดท้ายที่ถาม $dict\,$ แล้ว valid และต้องมีส่วนข้างหน้าของคำสุดท้ายนี้ที่สามารถตัดได้เหมือนกัน

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

ส่วนกรณีที่ $i\neq 0\,$ นั้น ถ้ามันจะตัดได้มันต้องเป็นกรณีที่อธิบายไปข้างต้น ดังนั้นสิ่งที่ต้องคิดต่อคือ ถ้าเรารู้แล้วว่ามันตัดได้ แล้วตำแหน่งเริ่มต้นของคำสุดท้าย ที่ทำให้คำนี้ valid และส่วนที่เหลือข้างหน้าตัดได้อีก ควรจะอยู่ตรงไหน สมมติให้เราสามารถตัดคำได้โดยแบ่งตำแหน่งของคำสุดท้ายกับกลุ่มคำที่อยู่ข้างหน้าที่ตำแหน่ง $k\,$ เราจะทำการลองทุก ๆ ค่า $k\,$ ที่เป็นไปได้ ดังนั้นเราจะได้ว่า $OPT(i)=\bigvee _{k=1}^{i-1}(OPT(k)\wedge dict(s[k+1,...,i]))\,$ ถ้า $i>0\,$

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

<geshi lang="c"> WORD(s,n)

   M[0] = 1
   for i = 1 to n do
       for k =1 to i-1 do
           if M[k] and dict(s[k+1,...,i])
               M[i] = 1
               break // ถ้ามีหนึ่งวิธีที่ตัดได้ก็หยุดเลย

</geshi>

<geshi lang="c"> FindSolution(i)

   if i = 0 then
       do nothing
   else
       for k = i - 1 downto 1 do
           if dict(s[k+1,...,i] and M[k]) then
               FindSolution(k) // ถ้าคำสุดท้ายตัดได้ ก็ต้องไปหาว่ากลุ่มคำที่อยู่ก่อนหน้าคำสุดท้ายที่ตัดได้นั้นตัดตรงตำแหน่งไหนต่อไป
                               print s[k+1,...,i] // พิมพ์คำสุดท้ายออกมา
               break

</geshi>