CareerCup

public static long numWays(int n){
	    long dp[] = new long[n];
	    dp[0] = 1;
	    dp[1] = 2;
	    for(int i = 2; i < n; i++){
	        dp[i] = dp[i-1] + dp[i-2];
	    }
	    return dp[n-1];
	}

public static long numWays(int n){
	    long dp[] = new long[n];
	    dp[0] = 1;
	    dp[1] = 2;
	    for(int i = 2; i < n; i++){
	        dp[i] = dp[i-1] + dp[i-2];
	    }
	    return dp[n-1];
	}

Simple DP solution
public static long numWays(int n){
long dp[] = new long[n];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}

public static long numWays(int n){
	    long dp[] = new long[n];
	    dp[0] = 1;
	    dp[1] = 2;
	    for(int i = 2; i < n; i++){
	        dp[i] = dp[i-1] + dp[i-2];
	    }
	    return dp[n-1];
	}

public static long numWays(int n){
	    long dp[] = new long[n];
	    dp[0] = 1;
	    dp[1] = 2;
	    for(int i = 2; i < n; i++){
	        dp[i] = dp[i-1] + dp[i-2];
	    }
	    return dp[n-1];
	}

public static long numWays(int n){
long dp[] = new long[n];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}

# n: number of columns to complete
    # bo: boolean, whether the bottom square at the current col is open
    # to: boolean, whether the top square at the current col is open
    # memo: cached results
    def rec(n, bo, to,memo)
      # return the cached result if we have one
      if memo.include?([n,bo,to])
        return memo[[n,bo,to]]
      end

      r = if bo && to # if both squares are open
        rec(n-1, true, true,memo) + # use a vertical piece
        rec(n-2, true, true,memo) + # use two horizontal pieces
        rec(n-1, false, true,memo) + # use an L piece, leaving top open
        rec(n-1, true, false,memo)   # use an L piece, leaving bottom open
      elsif bo  # if only the bottom is open
        rec(n-1, false, true,memo) + # use a horizontal piece, leave the top open
        rec(n-2, true, true,memo) # use an L shape to cover the bottom hole
      else # if only the top is open
        rec(n-1, true, false,memo) + # use a horizontal piece, leave the bottom open
        rec(n-2, true, true,memo) # use an L shape to cover the top hole
      end
      memo[[n,bo,to]] = r
      r
    end
    def solution(n)
      memo = {
      [1, true, true] => 1,
      [1, false, true] => 0,
      [1, true, false] => 0,
      [2, true, true] => 2,
      [2, true, false] => 1,
      [2, false, true] => 1}
      rec(n, true, true, memo)
    end