Dynamic programming

Dynamic programming builds up a table of the solutions to smaller sub-problems, until the desired solution is found. It is similar to recursive solutions, except that solutions are built up from the bottom up instead of broken from the top down.

Another difference is that in DP, solutions to sub-problems are stored in a table as they are computed. A recursive algorithm may make redundant calls to the same sub-problems. To make a recursive algorithm more like DP in this respect, a memo table can be used.

In Java, it is often convenient to use a string as the key to a memo table instead of writing your own key class and correctly overriding the equals and hashCode methods. For example, if the subproblems are indexed by two integers i and j, you can make the key String.format("%d,%d", i, j).