Абстрактный класс Java, реализующий интерфейс с обобщенными данными
Я пытаюсь определить абстрактный класс, реализующий Comparable. Когда я определяю класс со следующим определением:
public abstract class MyClass implements Comparable <MyClass>
подклассы должны реализовать compareTo (объект MyClass) . Вместо этого я хочу, чтобы каждый подкласс реализовывал compareTo (объект SubClass) , принимая объект своего собственного типа. Когда я пытаюсь определить абстрактный класс с помощью чего-то вроде:
public abstract class MyClass implements Comparable <? extends MyClass>
Он жалуется, что "
2 ответа
Существуют две типичные реализации подхода динамического программирования: снизу вверх и сверху вниз.
Динамическое программирование сверху вниз есть не что иное, как обычная рекурсия, дополненная запоминанием решений промежуточных подзадач. Когда данная подзадача возникает второй (третий, четвертый...) раз, она не решается с нуля, а вместо этого сразу же используется ранее заученное решение. Этот метод известен под названием мемоизация (без 'r' перед 'i').
Именно это и должен проиллюстрировать ваш пример с последовательностью Фибоначчи. Просто используйте рекурсивную формулу для последовательности Фибоначчи, но постройте таблицу значений fib(i) по пути, и вы получите алгоритм DP сверху вниз для этой задачи (так что, например, если вам нужно вычислить fib(5) во второй раз, вы берете его из таблицы, а не вычисляете снова).
В динамическом программировании снизу вверх подход также основан на хранении подрешений в памяти, но они решаются в другом порядке (от меньшего к большему), и результирующая общая структура алгоритм не является рекурсивным. Алгоритм LCS является классическим примером DP снизу вверх.
Алгоритмы DP снизу вверх обычно более эффективны, но их, как правило, сложнее (а иногда и невозможно) построить, поскольку не всегда легко предсказать, какие примитивные подзадачи вам понадобятся для решения всей задачи. исходная проблема, и какой путь вы должны выбрать от небольших подзадач, чтобы добраться до окончательного решения наиболее эффективным способом.
DP позволяет решить большую задачу, требующую больших вычислительных ресурсов, разбив ее на подзадачи, для решения которых требуется только знание непосредственно предшествующего решения. Вы получите очень хорошую идею, если возьмете Needleman-Wunsch и решите образец, потому что так легко увидеть приложение.
Обратный поиск кажется более сложным, когда дерево решений обрезается, если известно, что конкретный путь не даст оптимального результата.
Таким образом, можно сказать, что поиск с возвратом оптимизирует использование памяти, поскольку DP предполагает, что все вычисления выполнены, а затем алгоритм возвращается к узлам с наименьшей стоимостью.