What is Dynamic Programming?

Dynamic Programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. It is mainly used when the problem can be divided into overlapping subproblems and has an optimal substructure, meaning the optimal solution of the main problem can be obtained by using the optimal solutions of its subproblems.

How do we solve a DP Problem?

1. Define sub-problems and table for solution.
2. Find Recursive Relation between the solution of smaller problems and main solution.
3. Use an inductive method for constructing main solution by using the solution for smaller problems.

What is Memoization Approach?

Memoization / TopDown Approach: by storing the result of the recurring function, we reduce the number of function calls that the program makes, eventually reducing the time complexity for the given program. We generally do not use this approach !!

Floyd-Warshall Algorithm

Matrix Chain Multiplication

Optimal Binary Search Tree

Money Change Problem