package hsr.avatar;
import java.util.HashMap;


public class ModifiedPascalsTriangle {
    private HashMap<String, Integer> entries = new HashMap<String, Integer>();
    
    /**
     * Using modified pascals triangle, get the solution to M(q,k)
     */
    public int getEntry(int q, int k) {
        // check the cache
        if (entries.containsKey(q + "x" + k)) {
            return entries.get(q + "x" + k);
        }
        
        int value;
        
        if (k == 0) {
            // base case
            value = 1;
        } else if (k == q) {
            // other base case
            value = (int) Math.pow(2, q);
        } else {
            // calculate value recursively
            value = getEntry(q - 1, k) + getEntry(q - 1, k - 1);
        }
        
        // cache value
        entries.put(q + "x" + k, value);
        
        return value;
    }
}