How can a recursive Java method be memoized?

Question

So I've built this program to build different stair cases. Essentially the problem is: Given an integer N, how many different ways can you build the staircase. N is guaranteed to be larger than 3 and smaller than 200. Any previous step can not be larger than its following step otherwise it defeats the purpose of the staircase.

So given N = 3 You can build one staircase: 2 steps and then 1 step following that

Given N = 4 You can build one staircase: 3 steps and then 1 step following that

Given N = 5 You can build two staircases: 3 steps and then 2 steps OR 4 steps and then 1 step.

My method is below and it works, except its runtime is far too slow. So I was thinking of trying to make a memoization for the method, but to be honest I do not fully understand how to implement this. If I could get some help on how to do so that'd be great.

public static void main(String [] args)
{
    System.out.println(answer(200));
}
public static int answer(int n) { 
    return bricks(1,n) -1;
}
public static int bricks(int height, int bricksLeft)
{
    if(bricksLeft == 0)
    {
        return 1;
    }
    else if(bricksLeft < height)
    {
        return 0;
    }
    else
    {
        return bricks(height +1, bricksLeft - height) + bricks(height +1, bricksLeft);
    }
}

nhouser9 · Accepted Answer · 2017-02-18 07:53:58Z

Overview

So what you have here is a recursive solution. That works well for this type of problem. In this particular recursive solution, your recursive step will be called with the same arguments many times.

One really common optimization pattern for recursive solutions where the same calculation is being made many times is Dynamic Programming. The idea is that instead of doing the same calculation many times, we just cache each calculation the first time we do it. Then every following time, if we need to calculate the exact same value, we can just read the result from the cache.

Solution

With that in mind, this solution should work. It uses exactly the same logic as your original version, it just caches all results for the recursive step in a HashMap so that it never needs to calculate the same thing twice. It also uses a Staircase object to track pairs of (bricks, height). This is because we cannot insert pairs into a HashMap, we can only insert single objects.

Just change the variable bricks to whatever value you want to solve for.

public class Staircase {

    private static HashMap<Staircase, Integer> cache;

    public static void main(String[] args) {
        cache = new HashMap<>();
        int bricks = 6;
        Staircase toBuild = new Staircase(1, bricks);
        System.out.println(toBuild.waysToBuild() - 1);
    }

    public final int height;
    public final int bricksLeft;

    public Staircase(int height, int bricksLeft) {
        this.height = height;
        this.bricksLeft = bricksLeft;
    }

    public int waysToBuild() {
        if (cache.containsKey(this)) {
            return cache.get(this);
        }

        int toReturn;
        if (bricksLeft == 0) {
            toReturn = 1;
        } else if (bricksLeft < height) {
            toReturn = 0;
        } else {
            Staircase component1 = new Staircase(height + 1, bricksLeft - height);
            Staircase component2 = new Staircase(height + 1, bricksLeft);
            toReturn = component1.waysToBuild() + component2.waysToBuild();
        }

        cache.put(this, toReturn);
        return toReturn;
    }

    @Override
    public boolean equals(Object other) {
        if (other instanceof Staircase) {
            if (height != ((Staircase) other).height) {
                return false;
            }
            if (bricksLeft != ((Staircase) other).bricksLeft) {
                return false;
            }
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 73 * hash + this.height;
        hash = 73 * hash + this.bricksLeft;
        return hash;
    }
}

Analysis

I tested it out and the performance is much faster than your previous version. It computes values up to 200 instantly.

Your original function was O(2^n). That is because we make 2 recursive calls for each value from 1 to n, so the total number of calls is doubled for each time n is incremented.

The Dynamic Programming solution is O(n) since at most it will need to calculate the number of ways to make a staircase out of n bricks once for each value of n.

Additional Reading

Here is some more reading about Dynamic Programming: https://en.wikipedia.org/wiki/Dynamic_programming

This was by far, one of the best answers I've ever got on a question before. Thank you so very much for not only giving me a brief into the concept but as well linking it to my problem.
@GreenSkies Always happy to give a detailed answer to a well thought out question =]

Saurabh Srivastava · Accepted Answer · 2017-02-18 07:36:27Z

Use a small class to hold the pairs (height, bricks), say:

private static class Stairs {
    private int height;
    private int bricks;
    Stairs(int height, int bricks) {
        this.height = height; this.bricks = bricks;
    }
}

Then use a global HashMap<Stairs, Integer>, initialized in the main():

map = new HashMap<Stairs, Integer>();

In the bricks() function, check if the solution for a particular (height, bricks) pair is in the map. If yes, just return it from the map via a call to the get() method. Otherwise, do the computation:

Stairs stairsObj = new Stairs(height, bricks);
if(map.get(stairsObj) == null) {
    // Put your compute code here
}

Before every return statement in the function, add two additional statements. Something like:

int result = <whatever you are returning right now>;
map.put(stairsObj, result);
return result;

Collectives™ on Stack Overflow

How can a recursive Java method be memoized?

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related