Запоминание функции Java

Question

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

Поэтому, учитывая, N = 3 Вы можете построить одну лестницу: 2 шага, а затем 1 шаг после этого

Учитывая N = 4 Вы можете построить одну лестницу: 3 шага, а затем 1 шаг после этого

С учетом N = 5 Вы можете построить две лестницы: 3 ступени, а затем 2 шага ИЛИ 4 шага, а затем 1 шаг.

Моя функция внизу, и она работает, за исключением того, что ее время работы слишком медленное. Поэтому я думал о попытке сделать меморандум о функции, но, честно говоря, я не совсем понимаю, как это реализовать. Если бы я мог получить некоторую помощь в том, как это сделать, это будет здорово.

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

Обзора

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

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

Решение

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

Перед каждым оператором возврата в функции добавьте два дополнительных оператора. Что-то вроде:

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