Big-O Notation For Coding Interviews and Beyond/

...

/

Top Down and Bottom Up Approaches

Top Down and Bottom Up Approaches

This chapter continues the discussion on the complexity of dynamic programming problems.

We'll cover the following...

Solution

In the previous section, we discussed a recursive solution with exponential complexity. Now we'll look at two ways to solve the same problem, first using the DP top-down approach and then the DP bottom-up approach.

We saw in the recursive solution that subproblems are solved over and over again. We can store the solutions of the subproblems and avoid calculating them repeatedly. This is called memoization, where the algorithm remembers solutions to previously computed problems.

The only change required to make our recursive algorithm polynomial is to start storing the solutions to the subproblems; the necessary code appears below.

Top Down Implementation

Press + to interact
class Demonstration {
    
    static int[] computed;
    
    public static void main( String args[] ) {
        long start = System.currentTimeMillis();
        int n = 50;
        computed = new int[n + 1];
        for (int i = 1; i < n + 1; i++)
            computed[i] = -1;
        System.out.println(StringSumCount(n));
        long end = System.currentTimeMillis();
        System.out.println("Time taken = " + (end - start));
    }
    static int StringSumCount(int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 1) {
            return 0;
        }
        
        // If solution is already calculated
        if (computed[n] != -1)
            return computed[n];
        int sum = 0;
        // Number of ways to represent with 1
        sum += StringSumCount(n - 1);
        // Number of ways to represent with 2
        sum += StringSumCount(n - 2);
        // Number of ways to represent with31
        sum += StringSumCount(n - 3);
        computed[n] = sum;
        return sum;
    }  
}

Note that we can easily compute the value for n=50, but it will timeout if we try the same value for the recursive solution. Now let's try to reason ...