idea
Dynamics programming allows to process algorithm that require re-calculation of the same sub-problem several time. For example: fibonacci.
It works for problems where:
- Optimal sub-structure, i.e. it's solved exactly by solving subproblems
- Overlap of sub-problems, e.g. Fibo.
The idea is to instead calculate the subproblem only once and re-use.
Bottom-up = to calculate $Fibo(n)$, start with $F(1)$, then $F(2)$, etc., until reaching $F(n)$
public int Fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
var res1 = 1;
var res2 = 0;
for (var i = 2; i < n; i++) {
var res = res1 + res2;
res2 = res1;
res1 = res;
}
return res1 + res2;
}Top-down = calculate $Fibo(n)$, then store each of the sub results in a hash map not to recalculate.
public class Solution {
private Dictionary<int, int> memos = new Dictionary<int, int>();
public int Fib(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (memos.ContainsKey(n)) {
return memos[n];
}
return Fib(n - 1) + Fib(n - 2);
}
}