Dynamic Programming

The technique to divide problems into subproblems & making a judgment of solution based on solution of sub problems....

1. The problem should be able to be divided into smaller overlapping sub-problem.
2. An optimum solution can be achieved by using an optimum solution of smaller sub-problems.
3. Dynamic algorithms use memorization.

Sample Problems

1. Fibonacci number series
2. Knapsack problem
3. Tower of Hanoi
4. All pair shortest path by Floyd-Warshall
5. Shortest path by Dijkstra
6. Project scheduling

Optimal Binary Search

Weighted Job Scheduling

Given N jobs where every job is represented by following three elements of it.

1. Start Time
2. Finish Time
3. Profit or Value Associated

Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Knapsack Problem

Explanation: Knapsack problem is an example of 2D dynamic programming.

Applictaion 

Knapsack Based ECC Encryption and Decryption