Basic idea of DP is to :
1. Divide a problem into sub-problems
2. Solve those sub problems (save the solution for future reference)
3. Re-use those solutions.
This approach can be put to use when a given problem:
1. Holds the optimal substructure property
2. Can be divided into overlapping sub-problems ( sub-problems which tend to repeat ).
Since the solutions of sub-problems are saved, we can refer them instead of computing over and over again.
Let's better understand the concept by using Fibonacci program as an example. Given below is the algorithm:
Now let's draw a recursion tree for the above algorithm :
The highlighted sub-problems in the above tree overlap. Our algorithm recursively solves these sub problems, as in the above case F(n-3) and F(n-2) will be computed twice which is a waste of time. Applying DP approach to this problem would eliminate such unnecessary processing. When we encounter F(n-3) the second time we can simply refer to its solution computed earlier.
Dynamic Programming is very effective on such problems, as in the above case the running time of the algorithm is reduced from Exponential time to Linear time.
Dynamic Programming is very effective on such problems, as in the above case the running time of the algorithm is reduced from Exponential time to Linear time.
Challenge :
Modify the given Fibonacci algorithm by applying dynamic programming approach.
Hint: Use an array to save the solutions of all the sub-problems.
Hint: Use an array to save the solutions of all the sub-problems.