DYNAMIC PROGRAMMING = RECURSION(Overlapping Sub-Problems) + MEMORIZATION.
Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler sub-problems, solving each of those sub-problems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same sub-problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a modest expenditure in storage space. The technique of storing solutions to sub-problems instead of recomputing them is called MEMORIZATION.
Whether a problem can be solved using DP or not ?
Two Dynamic Programming properties which tells whether it can solve the given problem or not are :
- Optimal substructure : solution to a problem contain solution to sub-problems.
- Overlapping sub-problems : a recursive solution contains a small number of distinct sub-problems repeated many times.
Example :
Fibonacci Series
Fib(n) = 0, for n = 0
= 1, for n = 1
= Fib(n-1) + Fib(n-2), for n > 1
public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}
fib(5)
- fib(4) + fib(3)
- [fib(3) + fib(2)] + [fib(2) + fib(1)]
- [fib(2) + fib(1)] + [fib(1) + fib(0)] + [fib(1) + fib(0)] + fib(1)
- [fib(1) + fib(0)] + fib(1) + [fib(1) + fib(0)] + [fib(1) + fib(0)] + fib(1)
Time Complexity : O(2^n)
Here fib(2) was calculated 3 times (over-lapping of sub-problems). Since this problems has met both the properties of dynamic programming hence it can be solved using DP.
Instead of solving the same sub-problem again and again (here fib(2) 3 times) we can use memorization and store the previous calculated values then it reduces the complexity.
Now fib(n) using DP.
int fibMem[] = new int[n];
public int fib(int n) {
if (n == 1) return 1;
if (n == 2) return 1;
if (fibMem[n] != 0) return fibMem[n];
return fibMem[n] = fib(n-1) + fib(n-2);
}
Time Complexity : O(n) Space Complexity : O(n), for table.
//further improving
public int fib(int n) {
int a=0, b=1, sum, i;
for (i=0; i<n; i++) {
sum = a + b;
a = b;
b = sum;
}
return sum;
}
Time Complexity : O(n) Space Complexity : O(1)
Observations: While solving problems using DP, focus on the following:
- See how problems are defined in terms of sub-problems recursively.
- See if we can use some table[memorization] to avoid the repeated calculation.