Я пытаюсь выполнить динамическое программирование с возвратом максимальной суммы несмежных элементов, чтобы построить оптимальное решение для получения максимальной суммы.
Фон:
Сказать, если список ввода [1,2,3,4,5]
Запоминание должно быть [1,2,4,6,9]
И моя максимальная сумма равна 9, верно?
Мое решение:
Я нахожу первое вхождение максимальной суммы в памятке (поскольку мы можем не выбрать последний элемент) [это O(N)]
-
Затем я нахожу предыдущий элемент, выбранный по этой формуле:
max_sum -= a_list[index]
Как и в этом примере, 9 - 5 = 4, где 4 находится в индексе 2, мы можем сказать, что предыдущий выбранный элемент равен "3", который также находится в индексе 2 в списке ввода.
- Я нахожу первое вхождение 4, которое находится в индексе 2 (я нахожу первое вхождение из-за той же концепции на шаге 1, поскольку мы могли не выбрать этот элемент в некоторых случаях, когда есть несколько одинаковых сумм вместе) [Также O(N), но...]
Проблема:
Третий шаг моего решения выполняется в цикле while, скажем, несмежное ограничение равно 1, максимальная сумма, на которую мы должны вернуться, когда длина списка равна 5, составляет 3 раза, примерно N//2 раза.
Но 3-й шаг использует функцию индекса Python для поиска первого вхождения предыдущей_суммы [которое равно O(N)] memo.index(that_previous_sum)
Таким образом, общая временная сложность составляет около O(N//2 * N)
Что равно O(N^2) !!!
Правильно ли я понимаю временную сложность? Или я ошибаюсь? Есть ли более эффективный способ вернуться к списку запоминания?
П.С. Извините за форматирование, если я сделал это неправильно, спасибо!