Interesting problem with more thinking and less implementation. You can find hints and more discussion here : POI 10 Sums. Problem is from Polish Olympiad in Informatics.
A list of easy dp problems, which do not require any trick. These can be solved by straight forward dp approaches.
How to solve this probem? Can you give some hints. Probably it's a DP problem.