A3dp.java

package Algorithm;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class A3dp {
        private static final Map<BigInteger, BigInteger> memo = new HashMap<>();

    public static void main(String[] args) {
        BigInteger one = BigInteger.valueOf(1);
        BigInteger a = BigInteger.valueOf(8);
        
        long startTime = System.currentTimeMillis();
        System.out.println(startTime);
        for (BigInteger i = BigInteger.valueOf(0); i.compareTo(a) <= 0; i = i.add(one)) {
            BigInteger answer = RecurAlgorithm1(i);
            System.out.println("T(" + i + ") = " + answer);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Execution time: " + (endTime) + " milliseconds");
    }

    private static BigInteger RecurAlgorithm1(BigInteger a) {
        BigInteger zero = BigInteger.valueOf(0);
        BigInteger one = BigInteger.valueOf(1);
        BigInteger two = BigInteger.valueOf(2);

        // Base cases
        if (a.compareTo(zero) == 0 || a.compareTo(one) == 0) {
            return BigInteger.valueOf(2);
        }

        // Check if already calculated
        if (memo.containsKey(a)) {
            return memo.get(a);
        }

        // Recursive calculation with memoization
        BigInteger result = two.multiply(RecurAlgorithm1(a.subtract(one)))
                              .multiply(RecurAlgorithm1(a.subtract(two)));
        
        // Store in memo
        memo.put(a, result);
        return result;
    }
}