Making memoization less intrusive and more general
Kshitij Kythe
336
MemoizationexploreRecursion I

The Fibonacci Number question in 'Memoization' chapter asks to make memoization less-intrusive and more general using the decorator patter. I tried that and it worked for me, but I'm not sure if that's the way it was suppose to be done:

class Solution {
    
    public int fib(int n) {
        Fib memoFib = new MemoFibDecorator(new FibImpl());
        return memoFib.fib(n);
    }

}

interface Fib {
    public int fib(int n);
}

class FibImpl implements Fib {
    public int fib(int n) {
        if(n < 2)
            return n;
        else 
            return fib(n-1) + fib(n-2);
    }
}

abstract class FibDecorator implements Fib {
    protected Fib decoratedFib;
    
    public FibDecorator(Fib decoratedFib) {
        this.decoratedFib = decoratedFib;
    }
    
    public int fib(int n) {
        return decoratedFib.fib(n);
    }
}

class MemoFibDecorator extends FibDecorator {
    HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();
    
    public MemoFibDecorator(Fib decoratedFib) {
        super(decoratedFib);
    }
    
    public int fib(int n) {
        if(memo.containsKey(n)) {
            return memo.get(n);
        }
        int result;
        if(n < 2) {
            result = n;
        } else {
            result = fib(n-1) + fib(n-2);
            memo.put(n, result);
            
        }
        
        return result;
    }
}
Comments (0)