VietMX Staff asked 3 years ago
The key idea of DP is to save answers of overlapping smaller sub-problems to avoid recomputation. For that:
- An instance is solved using the solutions for smaller instances.
- The solutions for a smaller instance might be needed multiple times, so store their results in a table.
- Thus each smaller instance is solved only once.
- Additional space is used to save time.
