Recursion, DP, and the Duckworth–Lewis–Stern method - 5/7

Part - 4 is here.

The Top-Down Dynamic Programming (TDDP) code can be further optimized. In TDDP code, we use:

1. O(n) stack space due to recursive calls; and,
2. O(n) space for caching the result of those recursive calls.

By changing the code from recursive to iterative, we can save O(n) space right away. Further, by building the cache bottom-up, i.e., starting from the base case toward the top, we can eliminate the need for caching O(n) values.

Using both optimizations together, the space complexity of the code can be cut from O(n) to O(1). Let's put the code changes we did side by side for better understanding.

Comparing methods written to generate Fibonacci Number

Fibonacci number generator is written recursively as:

private static int fibonacciRecursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}        

Fibonacci number generator is written recursively with memoization (Top-down DP) as:

private static HashMap<Integer, Integer> fibCache = new HashMap<>(){{put(0, 0); put(1, 1);}};

private static int fibonacciMemoizedRecursive(int n) {
    if (fibCache.containsKey(n)) return fibCache.get(n);
    final int result = fibonacciMemoizedRecursive(n - 1) + fibonacciMemoizedRecursive(n - 2);
    fibCache.put(n, result);
    return result;
}        

Fibonacci number generator is written iteratively with memoization (Bottom-up DP; Also just iterative) as:

private static int fibonacciIterative(int n) {
    if (n == 0) return 0;
    int prev = 0, current = 1, temp;
    for (int i = 1; i < n; i++) {
        temp = current;
        current += prev;
        prev = temp;
    }
    return current;
}        

Comparing methods written for a three-step jumping robot

Three-step jumping robot is written recursively as:

private static int numberOfJumpsRecursive3(int steps) {
    if (steps == 1) return 1;
    if (steps == 2) return 2;
    if (steps == 3) return 4;
    return numberOfJumpsRecursive3(steps - 1)
            + numberOfJumpsRecursive3(steps - 2)
            + numberOfJumpsRecursive3(steps - 3);
}        

Three-step jumping robot is written recursively with memoization (Top-down DP) as:

private static HashMap<Integer, Integer> jumpCache = new HashMap<>(){{put(1, 1); put(2, 2); put(3, 4);}};

private static int jumpsRecursiveMemoized(int steps) {
    if (jumpCache.containsKey(steps)) return jumpCache.get(steps);
    final int jumps = jumpsRecursiveMemoized(steps - 1)
            + jumpsRecursiveMemoized(steps - 2)
            + jumpsRecursiveMemoized(steps - 3);
    jumpCache.put(steps, jumps);
    return jumps;
}        

Three-step jumping robot is written iteratively with memoization (Bottom-up DP) as:

private static long jumpsIterative(int steps) {
    if (steps == 1) return 1;
    if (steps == 2) return 2;
    if (steps == 3) return 4;
    long current, jumps = 4, prevJumps = 2, prevPrevJumps = 1;
    for (int i = 4; i <= steps; i++) {
        current = jumps + prevJumps + prevPrevJumps;
        prevPrevJumps = prevJumps;
        prevJumps = jumps;
        jumps = current;
    }
    return jumps;
}        

• The benefit of a recursive solution to the above problems is that it is intuitive. And the recursive solution is intuitive because the above problems are naturally recursive.
• The benefit of recursion with memoization (Top-down DP) over the original recursive solution is that it lets us cut down the runtime complexity from O(c^n) to O(n).
• Finally, the benefit of iterative with memoization (Bottom-up DP) over Top-down DP is that it lets us cut down the space complexity from O(n) to O(1).

So, when a recursive code that has overlapping problems is converted to its 'iterative with memoization' version, we get:

1. A runtime complexity improvement of O(n) from O(c^n); and,
2. A space complexity improvement of O(1) from O(n).

Understanding the space complexity improvement

I called the Top-down DP and Bottom-up DP versions of the code for increasingly higher input values to find the input value where the Top-down DP code broke down.

Initially, I had to change the return type of these methods to Long from Integer because, for higher inputs, the returned number was more than 4 bytes in size. Thus Integer was wrapping around and returning negative values.

Later, even Long started returning negative values. I didn't bother changing because accuracy was not the concern here. The task is to find when the recursive solution starts giving stack overflow error.

• Top-down DP failed for a staircase height of 8450 steps because of stack overflow. The iterative version continued to answer until Integer.MAX_VALUE high staircase even though it was now returning garbage values.
• Top-down DP failed to calculate the 8290th Fibonacci number because of stack overflow. The iterative version continued to answer until Integer.MAX_VALUE, in this case also, returning garbage values for higher input.

The configuration used for running all of the above tests/codes is:

• macOS Ventura 13.0.1;
• openjdk 17.0.2 2022-01-18;
• Apple M1 Max with LPDDR5 32 GB RAM.

The iterative/Bottom-up DP code can also be described by simple mathematical equations.

The equation for the Fibonacci number is well-known:

The equation for a three-step jumping robot would be written as follows:

The Duckworth-Lewis-Stern method uses Dynamic Programming to compute the resources left for the team for each {ball, wicket} combination, with balls going from 300 to 0 and wickets going from 10 to 1.

Part - 6 is here.