Remembering the Java Function

Question

So, I built this program to create different stairwells. Essentially the problem is this: given the integer N, how many different ways you can build a staircase. N is guaranteed to be more than 3 and less than 200. Any previous step cannot be more than the next step, otherwise it will defeat the goal of the ladder.

Thus, with N = 3, you can build one staircase: 2 steps, and then 1 step following

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

With N = 5, you can build two stairs: 3 steps, and then 2 steps OR 4 steps, and then 1 step.

My function is lower and it works, except that its execution time is too slow. So I was thinking of trying to make a memorandum of function, but to be honest, I don’t quite understand how to implement this. If I could get some help on how to do this, that would 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);
    }
}

Answer 1

Overview

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

, - . , , , , . , , , .

, . ​​ , , HashMap, . Staircase (, ). , HashMap, .

bricks , .

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;
    }
}

, . 200.

O(2^n). , 2 1 n, , n .

O(n), n n.

: https://en.wikipedia.org/wiki/Dynamic_programming

Answer 2

(, ), :

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

HashMap<Stairs, Integer>, main():

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

bricks() , (, ) . , get(). :

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

return . - :

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