Blog Post

In the Dynamic Programming,

1. We divide the large problem into multiple subproblems.

2. Solve the subproblem and store the result.

3. Using the subproblem result, we can build the solution for the large problem.

4. While solving the large problem, if the same subproblem occurs again, we can reuse the already stored result rather than recomputing it again. This is also called memoization.

Dynamic Programming Approaches

1. Bottom-Up approach

2. Top-Down approach

Bottom-Up approach

Start computing result for the subproblem. Using the subproblem result solve another subproblem and finally solve the whole problem.

Example

Let's find the nth member of a Fibonacci series.

Fibonacci(0) = 0

Fibonacci(1) = 1

Fibonacci(2) = 1 (Fibonacci(0) + Fibonacci(1))

Fibonacci(3) = 2 (Fibonacci(1) + Fibonacci(2))

We can solve the problem step by step.

1. Find Oth member

2. Find 1st member

3. Calculate the 2nd member using 0th and 1st member

4. Calculate the 3rd member using 1st and 2nd member