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
1. Bottom-Up approach
Start computing result for the subproblem. Using the subproblem result solve another subproblem and finally solve the whole problem.
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
5. By doing this we can easily find the nth member.
1. set Fib = 0
2. set Fib = 1
3. From index 2 to n compute result using the below formula
Fib[index] = Fib[index - 1] + Fib[index - 2]
4. The final result will be stored in Fib[n].
Top-Down breaks the large problem into multiple subproblems.
if the subproblem solved already just reuse the answer.
Otherwise, Solve the subproblem and store the result.
Top-Down uses memoization to avoid recomputing the same subproblem again.
Let's solve the same Fibonacci problem using the top-down approach.
Top-Down starts breaking the problem unlike bottom-up.
If we want to compute Fibonacci(4), the top-down approach will do the following
Fibonacci(4) -> Go and compute Fibonacci(3) and Fibonacci(2) and return the results.
Fibonacci(3) -> Go and compute Fibonacci(2) and Fibonacci(1) and return the results.
Fibonacci(2) -> Go and compute Fibonacci(1) and Fibonacci(0) and return the results.
Finally, Fibonacci(1) will return 1 and Fibonacci(0) will return 0.
Fib(4) / \ Fib(3) Fib(2) / \ / \ Fib(2) Fib(1) Fib(1) Fib(0) / \ Fib(1) Fib(0)
We are computing the result of Fib(2) twice.
This can be avoided using memoization.
If n == 0 || n == 1 return n;
Otherwise, compute subproblem results recursively.
return Fib(n-1) + Fib(n-2);
Visual Representation of the above algorithm
Optimizing the above program using memoization
1. Declare an array to store the subproblem results. i.e. result
2. Initialize the array to -1. -1 indicates that the subproblem needs to be computed.
3. if result[N] == -1
compute and store it in result[N] using above algorithm.
return the already computed result directly.