Can anyone help me with the question ??

I was recently studying the tries data structure. I found this question on SPOJ. I also went through this topcoder thread but was unable to understand how DP was used.

Also this link mentions that this question can be solved using Tries and DP. So please explain