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.

Link to problem (updated): https://szkopul.edu.pl/problemset/problem/4CirgBfxbj9tIAS2C7DWCCd7/site/?key=statement.

A list of easy dp problems, which do not require any trick. These can be solved by straight forward dp approaches.

1. Codeforces - #260 div1 A
2. SPOJ ACODE
3. SPOJ ADFRUITS
4. Codeforces - #89 div2 D
5. SPOJ BEHAPPY
6. SPOJ EDIST
7. SPOJ DIEHARD
8. SPOJ IOIPALIN
9. Codeforces - #271 div2 D

How to solve this probem? Can you give some hints. Probably it's a DP problem.