Dynamic Programming

Dynamic Programming is formulated upon recursion. In solving a problem you need to take decisions, for every decision if you can answer the question by comparing two outcomes of the decision instead of following a path irreversibly (what we do in the greedy approach) it is called dynamic programming. Also the solutions of the two outcomes must be expressed as solving the same problem (before the decision) but with smaller inputs. This is called expressing the problem as solution of sub-problems.

Naive Approach

1. Express the problem as combination of sub-problems at a decision step.
2. Establish base conditions.
3. Solve the sub-problems recursively.

DYNAMIC PROGRAMMING

In the naive approach we solve the same sub-problems again and again and also the overhead for recursion is large. One approach is to store answers for every sub-problem and look up every time when we solve another.Analogy: Going to all eaves starting from root evaluating each path. Another approach called BOTTOM-UP is based on predicting the interaction between sub-problems and simulating them starting from base case. Analogy starting from leaves and reaching root.