Skip to main content

Dynamic Programming

Learn Dynamic Programming (Algorithms, Programming Fundamentals) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Dynamic Programming (DP) is a technique for solving problems by breaking them into overlapping sub-problems, solving each sub-problem only once , and reusing (caching) the result the next time it's needed. DP applies when a problem has: • Overlapping sub-problems - the same smaller problem is solved again and again. • Optimal substructure - the overall solution can be built from optimal solutions to sub-problems. There are two ways to implement DP: • Memoization (top-down) - recursion + a cache. • Tabulation (bottom-up) - an iterative table built from the smallest sub-problem upward.

More lessons in Algorithms