Dynamic Programming is a Programming Paradigm. If you have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again.
Ways of solving such Problems
-
Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.
-
Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.
See also:
- Dynamic Programming is not black magic - blog post on solving an Advent Of Code problem using Dynamic Programming