Dynamic algorithm Programming

Dynamic programming

Invented in the 1957 by Richard Bellman as a general method for optimizing multistage decision processes

The term “programming” refers to a tabular method.

Often used for optimization problems.

Solves problems by combining the solutions to subproblems that contain common sub-sub-problems.

Difference between DP and Divide-and-Conquer

Using Divide and Conquer to solve these problems is inefficient as the same common sub-sub-problems have to be solved many times.

DP will solve each of them once and their answers are stored in a table for future reference.

Example: Fibonacci numbers, Matrix multiplication optimization, Longest Common Subsequence

Tweet