เรียกค่าที่เพื่อนของเราคิดเอาไว้ว่า "ค่าคำตอบ" หากเราทราบว่าค่าคำตอบเป็นจำนวนเต็มที่อยู่ในช่วง $[l, r]$ แล้วเราถามค่า $x$ เพื่อนไป เราจะสามารถแบ่งได้ออกเป็น 3 กรณีได้แก่

1. เพื่อนตอบว่า "ใช่" ดังนั้น $x$ เป็นค่าคำตอบ
2. เพื่อนตอบว่า "เลขที่คิดมีค่าน้อยกว่า $x$" ดังนั้น ค่าคำตอบอยู่ในช่วง $[l, x - 1]$
3. เพื่อนตอบว่า "เลขที่คิดมีค่ามากกว่า $x$" ดังนั้น ค่าคำตอบอยู่ในช่วง $[x + 1, r]$

หาก $l = r$ จะมีเพียงกรณีที่ 1 เท่านั้นที่เป็นไปได้ แต่หาก $l \neq r$ ในกรณีที่แย่ที่สุด จะเป็นไปได้เพียงกรณีที่ 2 หรือ 3 เท่านั้น ทั้งนี้ไม่ว่ากรณีไหน เราก็ต้องจ่ายเงิน $C_x$ เหมือนกัน

เราจะใช้ Dynamic Programming ในการคำนวณคำตอบ กำหนดให้ $dp(i, j)$ คือเงินที่น้อยที่สุดที่เราต้องจ่ายในกรณีที่แย่ที่สุดเมื่อทราบอยู่แล้วว่าค่าคำตอบอยู่ภายในช่วง $[i, j]$

• $dp(i, i) = C_i$ สำหรับ $1 \leq i \leq N$ เป็น Base Case ตามที่ได้กล่าวไว้ในย่อหน้าที่แล้ว
• $dp(i, j) = 0$ เมื่อ $i > j$
• $dp(i, j) = \min \limits_{i \leq k \leq j} \{C_k + \max(dp(i, k - 1), dp(k + 1, j))\}$

หากเราทายเลข $k$ ในกรณีที่แย่ที่สุดจะเป็นกรณี 2 หรือ 3 กรณีใดกรณีหนึ่งที่ทำให้เราจะต้องจ่ายเงินมากที่สุด นั่นคือ $\max(dp(i, k - 1), dp(k + 1, j))$ แต่เนื่องจากเราสามารถเลือกถามค่าใดๆ ก็ได้ที่อยู่ภายในช่วง $[i, j]$ เราจึงควรเลือกค่าที่ทำให้เราจ่ายเงินน้อยที่สุดนั่นเอง

Time Complexity: $\mathcal{O}(N^3)$