Как можно запомнить рекурсивный метод Java?

Обзор

Итак, у вас есть рекурсивное решение. Это хорошо работает для этого типа проблемы. В этом конкретном рекурсивном решении ваш рекурсивный шаг будет вызываться с одними и теми же аргументами много раз.

Одним из действительно распространенных шаблонов оптимизации для рекурсивных решений, когда одни и те же вычисления выполняются много раз, является динамическое программирование. Идея состоит в том, что вместо многократного выполнения одних и тех же вычислений мы просто кэшируем каждое вычисление при первом его выполнении. Затем каждый следующий раз, если нам нужно вычислить одно и то же значение, мы можем просто прочитать результат из кеша.

Решение

Имея это в виду, это решение должно работать. Он использует ту же логику, что и ваша исходная версия, он просто кэширует все результаты для рекурсивного шага в 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

Используйте небольшой класс, чтобы удерживать пары (высота, кирпичи), скажем:

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;