Dynamic programming where a big problem is divided into small subproblems and solve those subproblems . Use the previous optimal solution of subproblems .
Lets see an example ,
public class Fibonacci {
public static int fib(int n, Map<Integer, Integer> memo) {
if (memo.containsKey(n))
return memo.get(n);
if (n <= 2)
return 1;
memo.put(n, fib(n - 1, memo) + fib(n - 2, memo));
return memo.get(n);
}
public static void main(String[] args) {
int number = 9;
Map<Integer, Integer> memo = new HashMap<>();
int result = fib(number, memo);
System.out.println(result);
}
}
Here we use memorization , so the previously solved subproblems are stored into the memory and we can use it . What will minimize the time complexity. So, the time complexity reduces from exponential to linear .
