Dynamic Programming is similar to Recursion in which we break the problem into subproblems and use them to arrive at the final solution. However, it is different from Recursion as we store results of already solved subproblems to avoid re- calculation. Caching of results leads to better time complexity of code at the cost of space complexity. Let us start with a recursive solution:
Dynamic Programming approach will be caching the solved sub problems and will be more efficiently execute in linear time.
public int fibonacci1(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci1(n - 1) + fibonacci1(n - 2);
}
}
Recursive Computation involves lot of redundancy as instead of reusing a sub problem already solved(F(0) and F(1)) we are recalculating it. This algo will have Exponential time complexity.Dynamic Programming approach will be caching the solved sub problems and will be more efficiently execute in linear time.
public int fibonacci2(int n) {
int[] table = new int[n + 1];
for (int i = 0; i < table.length; i++) {
if (i == 0) {
table[i] = 0;
} else if (i == 1) {
table[i] = 1;
} else {
table[i] = table[i - 2] + table[i - 1];
}
}
return table[n];
}
Two characteristics to look for before choosing Dynamic Programming approach:
- Overlapping Sub problems: Tree shown above shows overlapping subproblem (F(0) and F(1)). In order to better understand this let us consider another problem: Calculate the Factorial of a number. Factorial(n) = n * Factorial(n-1). Factorial(5) = 5 *Factorial(4) = 5 * 4 * Factorial(3) = 5*4*3*2*1. Here, sub problem is Factorial(n-1) and hence non overlapping. Let us modify above problem: Calculate Factorial of all numbers between 1 and 50. In this case sub problems will be overlapping.
- Optimal Sub Structure: Optimal solution of problem can be calculated easily once we have an optimal solution to sub problems.
Do share your experiences !!!!
References:
References:
