Memorization

 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 .