Your niece was given a set of blocks for her birthday, and she has decided to build a panel using 3”×1” and 4.5”×1" blocks. For structural integrity, the spaces between the blocks must not line up in adjacent rows. For example, the 13.5”×3” panel below is unacceptable, because some of the spaces between the blocks in the first two rows line up (as indicated by the dotted line).
There are 2 ways in which to build a 7.5”×1” panel, 2 ways to build a 7.5”×2” panel, 4 ways to build a 12”×3” panel, and 7958 ways to build a 27”×5” panel. How many different ways are there for your niece to build a 48”×10” panel? The answer will fit in a 64-bit integer. Write a program to calculate the answer.



Here is My code. I'm using recursion for this program, it works well for the small numbers, but once we get to the larger number the program hangs.

Please let me know if there is a way to convert the recursive portion of the code into dynamic programming code or if I'm missing something that will help me speed this up.


Thank you.
---------------------------------------------------------------------------------------------------------------------------
------------------------------------------------ Code Bellow ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


import java.util.*;


public class BlockWall {

@SuppressWarnings("unchecked")
public static void main(String[] args) {
String WIDTH_STRING = args[0]; //48
String HEIGHT_STRING = args[1]; //10
double WIDTH = Double.parseDouble(WIDTH_STRING);
double HEIGHT = Double.parseDouble(HEIGHT_STRING);
List currrow = new ArrayList();
List<List<Double>> rows = new ArrayList<List<Double>>();
boolean[][] conflict;
makeRow(0, WIDTH, currrow, rows);
conflict = new boolean[rows.size()][rows.size()];
findConflicts(rows, conflict);
List<List<Double>> wall = new ArrayList<List<Double>>();
long startTime = System.currentTimeMillis();
System.out.println(makeWall(0, HEIGHT, wall, rows, conflict));
long endTime = System.currentTimeMillis();
System.out.println("That took " + (endTime - startTime) + " milliseconds");
}

/*
* current = 0 ; #which is the bricks needed for the row
*/
// static void makeRow(double current, double width, List<Double> currentrow, List<List<Double>> rows){
static void makeRow(double current, double width, List<Double> currentrow, List<List<Double>> rows){

//check when to see if the total bricks added are larger than the width of the row
if ( current >= width){
if ( current == width){
//create list reference back to current row
List<Double> row = new ArrayList<Double>(currentrow);

//remove the extra brick from the end of the row
row.remove(row.size()-1);

//creates a row for the wall
//rows keep track of all the possible combinations of bricks for a wall
rows.add(row);
}
}//if
else{

/*
* First we check to see if the row is empty
* if(empty) then we add our first brick (3.0)
* for the second iteration we add the second brick (4.5)
* and so forth until current >= width
*/
for(double size = 3.0; size <= 4.5; size = size + 1.5){
current = current + size;
if ( currentrow.size() == 0){
currentrow.add(current);
}
else{
currentrow.add(current);
}
makeRow(current, width, currentrow, rows);
//removes the last brick added from the row and from current
currentrow.remove(currentrow.size()-1);
current = current - size;
}
}
}//makeRow



/*
* Checks to see if any of the rows have adjacent bricks
* using 2 nested for loops
*
*/
private static void findConflicts(List<List<Double>> rows, boolean[][] conflict) {
for(int i = 0; i < rows.size(); i++){
for(int j = 0; j < rows.size(); j ++){
conflict[i][j] = false;
List arow = rows.get(i);
if ( rows.get(i).contains(arow.get(j))){
conflict[i][j] = true;
break;
}
}
}
}//findConflicts


private static long makeWall(int i, double HEIGHT, List<List<Double>> wall, List<List<Double>> rows, boolean[][] conflict) {
if ( i == HEIGHT){
return 1;
}
else{
long count = 0;
for(int j = 0; j < rows.size(); j ++){
List<Double> arow = rows.get(j);
if ( doesNotConflict(arow, wall)){
wall.add(arow);
count = count + makeWall(i+1, HEIGHT, wall, rows, conflict);
wall.remove(wall.size()-1);
}
}
return count;
}
}

//checks to see if adjacent rows do not have adjacent bricks
private static boolean doesNotConflict(List<Double> arow, List<List<Double>> wall) {
if ( wall.size() == 0)
return true;
else{
List<Double> wallRow = wall.get(wall.size()-1);
for(int i = 0; i < arow.size(); i ++){
if ( wallRow.contains(arow.get(i))){
return false; //if a match is found returns a conflict
}
}
return true;
}
}
}