What is memoization? explain with an example

Memoization is one of the dynamic programming method. This technique stores previous relevant computation result and reuse them whenever required. It is like you have a scratchpad and write down each solution once it is derived. and reuse it later to derive other solutions whenever required.

For ex. Every Fibonacci number is calculated from previous two Fibonacci numbers, So If you are writing a program to calculate Fibonacci series memoization technique will help in increasing the overall program speed.

Steps to find out the 5th Fibonacci number without memoization

// Fib(5)

Step 1: fib(0) + fib(1)
Step 2: fib(1) + fib(2)
Step 3: fib(2) + fib(3)
Step 4: fib(3) + fib(4)
Step 5: fib(4) + fib(5)

In order to find 5th Fibonacci number we need to find previous 4 Fibonacci numbers first. Here If we observe closely every sub problem being solved two times except fib(1) & fib(5). This type of problems are called overlapping sub-problems. That means we are going to execute code to solve same problem multiple times which would increase the execution time. Instead we can use memoization technique to store solutions for all the subproblems when it is calculated first time and then reuse it when it is needed later as below

Steps to find out the 5th Fibonacci number with memoization

// Fib(5)
Step 0: fib(1) = 1              // save fib(1)      ;  known base condition
Step 1: fib(1) + fib(2)         // reuse fib(1), fib(2)
Step 2: fib(2) + fib(3)         // reuse fib(2), save fib(3)
Step 3: fib(3) + fib(4)         // reuse fib(3), save fib(4)
Step 3: fib(4) + fib(5)         // reuse fib(4), save fib(5)

In every step we are storing unknown solutions and reusing known solutions. Below is the Java version of the solution.

package in.questionsforinterview.problems;

import java.util.HashMap;
import java.util.Map;

public class Tester {

	public static void main(String[] args) {

		System.out.println(fibonacciMemoize(10));

	}

	private static Map<Integer, Integer> memoizationStore = new HashMap<>(); // O(1)

	// Fibonacci with Memoization
	public static int fibonacciMemoize(int n) {

		if (n == 0)
			return 0;
		if (n == 1)
			return 1;

		if (memoizationStore.containsKey(n)) {
			System.out.println("Reusing : " + n);
			return memoizationStore.get(n);
		}

		int result = fibonacciMemoize(n - 1) + fibonacciMemoize(n - 2);

		System.out.println("Saving : " + n);
		
		memoizationStore.put(n, result);

		return result;

	}
}

//Output

//Saving : 2
//Saving : 3
//Reusing : 2
//Saving : 4
//Reusing : 3
//Saving : 5
//Reusing : 4
//Saving : 6
//Reusing : 5
//Saving : 7
//Reusing : 6
//Saving : 8
//Reusing : 7
//Saving : 9
//Reusing : 8
//Saving : 10
//55