public class ParkingLot { /** * * @param n>0 size of the parking lot * @return the number of ways we can park: * Explorers: size 2 * Civics: size 1 * in a parking lot of size n > 0 * */ public long parkingLot(int n) { // System.out.println("parkingLot(" + n + ")"); if (n == 1) return 1; // a Civic else if (n == 2) return 2; // an Explorer or two Civics else return parkingLot(n-2) // An Explorer in last position + parkingLot(n-1); // A Civic in last position } /** * * @param n>0: size of parking lot * @param A: array of solved parking lot problems * @return the number of ways we can park: * Explorers: size 2 * Civics: size 1 * in a parking lot of size n > 0 */ public long parkingLot (int n, long [] A) { //System.out.println("fast Lot(" + n + ")"); if (A[n] == 0) { // you haven't already solved this subproblem if (n == 1) A[n] = 1; // C else if (n == 2) A[n] = 2; // E ;CC else A[n] = parkingLot(n-2,A) // Excursion in last position + parkingLot(n-1,A); // Civic in last position } return A[n]; } public static void main(String[] args){ ParkingLot P = new ParkingLot(); for(int i = 1; i < 50; i++){ long[] lot = new long[i+1]; System.out.print("Fast lot "+i+": "); System.out.println(P.parkingLot(i,lot)); System.out.print("Slow lot "+i+": "); System.out.println(P.parkingLot(i)); } } }