Dynamic programming is a technique for solving problems with the following properties:

- An instance is solved using the solutions for smaller instances.
- The solution for a smaller instance might be needed multiple times.
- The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
- Additional space is used to save time.

This example perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.