Лучший способ сохранить результаты - динамическое программирование

Question

Я работаю над решением проблемы, которая немного похожа на Проблема Эйлера 215 . Я думаю, что могу объяснить это без объяснения всей проблемы и / или моего полного подхода к ее решению.

Прямо сейчас я делаю рекурсивные вызовы с помощью RT ([Arraylist of numbers], int i). В соответствии с методикой, я хочу сохранить результаты, поэтому, если и когда RT запрашивает ту же проблему, я могу просто найти ответ вместо повторения, пока не будет достигнут базовый вариант.

Просто для иллюстрации RT ([3, 7,5, 10,5, 15], 2). В рекурсии, справа в правой части, чтобы увеличить. Arraylist используется для определения того, что еще нужно вспомнить в базовом случае.

Как правило, в моем понимании динамического программирования обычно используются 2D-массивы, в которых результаты сохраняются и сохраняются с использованием того, что называется контрольной точкой. Это замечательно, если это что-то вроде RT (int x, int y). Но как насчет моей проблемы?

Полагаю, я могу изменить ArrayList на строку 37510515, а затем на некоторые использованные числа ASCII или, возможно, сами числа. Но я надеюсь, что смогу подойти к этому, как к HashMap, где я использую ArrayList в качестве ключа, но недостаток в этом HashMap хорошо работает только с одним значением (я знаю, что могу связать, но как это будет работать при сохранении результатов, пока легко отследить, к какому "int i" оно относится?)

Короче говоря, может ли кто-нибудь помочь мне придумать способ сохранить результаты с ArrayList и int в качестве двух ссылок?

Заранее спасибо!

Answer 1

Вы можете использовать объекты любого класса в качестве ключей для HashMap, и он будет работать, если объект правильно определил equals () и hashCode ().Эти методы уже правильно реализованы в ArrayList, поэтому вы должны обнаружить, что использование ArrayLists в качестве ключей HashMap работает очень хорошо.

Если вы хотите использовать ArrayList и число, объединенное в качестве ключа для HashMap, вы можетелибо определите для этого класс, реализуя в этом классе hashCode () и equals (), либо немного обманите, сделав число последней записью в массиве.

Похоже, что вы делаете большекак http://en.wikipedia.org/wiki/Memoization, чем динамическое программирование, но оно может выполнить свою работу - я полагаю, что задача Эйлера была установлена ​​для того, чтобы сделать ее выполнимой для лучшего метода - если это запоминание или динамическое программирование, вы должны найти его доступным,Это займет слишком много времени, тогда мы оба пропустили какой-то более эффективный метод.

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

Answer 2

Один из способов решить эту проблему - реализовать собственный класс, заключающий в себе как arraylist, так и int, записывающий hashCode и equals, как указано здесь.

Использование байтового массива в качестве ключа карты