Solution in Java to solve the Climb Stairs problem in Leetcode.com

leetcode_climb_stairs.java

public class Solution {
    
    private Map<Integer, int[]> pows = new HashMap<Integer, int[]>();
    
    {
        pows.put(1, new int[]{1, 1, 1, 0});
    }
    
    private int[] pow(int n) {
        if (pows.containsKey(n)) return pows.get(n);
        int[] r = sqr(pow(n/2));
        if (n % 2 == 1) {
            r = mult(r, pows.get(1));
        }
        pows.put(n, r);
        return r;
    }
    
    private int[] sqr(int[] a) {
        return mult(a, a);
    }
    
    private int[] mult(int[] a, int [] b) {
        int[] c = new int[4];
        c[0] = a[0]*b[0] + a[1]*b[2];
        c[1] = a[0]*b[1] + a[1]*b[3];
        c[2] = a[2]*b[0] + a[3]*b[2];
        c[3] = a[2]*b[1] + a[3]*b[3];
        return c;
    }
    
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] matrix = pow(n-2);
        return 2*matrix[0] + matrix[1];
    }
}