Dp problem

http://poj.org/problem?id=2915 so, this is a poj problem that has a DP solution. if anybody could give any hints, would be much appreciated

I am looking for an explanation too,
Found this code http://ideone.com/CmSMbv But couldn’t really understand it.
If someone could point me to an editorial of a similar type problem or so, It would be great.

https://github.com/Linzertorte/POJ/blob/master/2915Zuma.cpp here’s another solution, a shorter one, but still can’t understand it. I even found an analysis of the problem, but in chinese

Please update this thread if you find any editorial equivalent .

//