"Naive" recursion vs. Dynamic Programming, Java

"Naive" recursion vs. Dynamic Programming

//Title of this code
//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_45

/* This is a little test of the wall clock running time of
 * two solutions to "Cracking the Coding Interview" 9.1.
 * The first solution (numWays()) is a top down recursive
 * solution to the problem with running time of O(3^n).
 * The second solution (numWaysDP()) is essentially the same
 * solution but the results of subproblems are cached instead of
 * being recomputed with every recursive call.
 * Runtime analysis: O(n) time (maybe? not sure) O(n) space.
 *
 * NOTE: A parameter greater than 36 causes an int overflow.
 */

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        // init map for the DP soln
        int[] map = new int[50];
        for (int i = 0; (i < map.length); i++) {
            map[i] = -1;
        }
        
        // run and time naive soln
        long start = System.currentTimeMillis();
        System.out.println(numWays(34));
        long end = System.currentTimeMillis();
        System.out.println("Running time: " + (end - start));
        
        // run and time DP soln
        start = System.currentTimeMillis();
        System.out.println("DP soln: " + numWaysDP(34, map));
        end = System.currentTimeMillis();
        System.out.println("Running time: " + (end - start));
    }
    
    // naive soln
    private static int numWays(int n) {
        if (n < 0) return 0;
        if (n == 0) return 1;
        else return numWays(n - 1) + numWays(n - 2) + numWays(n - 3);
    }
    
    // DP soln
    private static int numWaysDP(int n, int[] map) {
        if (n < 0) return 0;
        if (n == 0) return 1;
        if (map[n] > -1) return map[n];
        
        map[n] = numWaysDP(n - 1, map) + 
                 numWaysDP(n - 2, map) + 
                 numWaysDP(n - 3, map);
        return map[n];
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development