Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map, etc). Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup. So the next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time.
Dynamic programming algorithms are used for optimization (for example, finding the shortest path between two points, or the fastest way to multiply many matrices). A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Some greedy algorithms (such as Kruskal's or Prim's for minimum spanning trees) are however proven to lead to the optimal solution.
Dynamic programming and divide and conquer are similar. Both are recursive and both solve sub-problems. However, divide and conquer combines solutions to sub-problems to form solutions to larger problems, whereas dynamic programming combines solutions to sub-problems to form solutions to even larger problems. Dynamic programming is used when the sub-problems are not independent, whereas divide and conquer is used when the sub-problems are independent.
Dynamic programming and greedy algorithms are similar. Both are optimization methods and both solve sub-problems. However, greedy algorithms make the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. Dynamic programming, on the other hand, does not necessarily make the optimal choice at each step. It attempts to solve the sub-problems first and then uses the solutions to the sub-problems to solve the overall problem. Dynamic programming is used when the sub-problems are not independent, whereas greedy algorithms are used when the sub-problems are independent.
- Climbing Stairs | Easy | Solution | Problem Description
- Min Cost Climbing Stairs | Easy | Solution | Problem Description
- House Robber | Medium | Solution | Problem Description
- House Robber II | Medium | Solution | Problem Description
- Longest Palindromic Substring | Medium | Solution | Problem Description
- Palindromic Substrings | Medium | Solution | Problem Description
- Decode Ways | Medium | Solution | Problem Description
- Coin Change | Medium | Solution | Problem Description
- Maximum Product Subarray | Medium | Solution | Problem Description
- Word Break | Medium | Solution | Problem Description
- Longest Increasing Subsequence | Medium | Solution | Problem Description
- Partition Equal Subset Sum | Medium | Solution | Problem Description
Category: Dynamic Programming
Status: Done
Author: David Bujosa