any ideas about the algorythm?
I used DP but it's tle-ing on #6 :(
Try to do some improvements to your DP. You don't need to do complete DP.
I used DP with recursion. At first it got TLE#5. First improvement led to TLE#6. Second improvement - TLE#11.
Finaly after last improvement I got AC in 0.703sec and 146KB
But another, better algorithm exists ;)