Моя задача - решить проблему чередующейся подстроки с помощью рекурсивного динамического программирования:
Рассмотрите последовательность A = a1, a2, a3, ... an целых чисел. Подпоследовательность B последовательности a — это последовательность B = b1, b2, ....,bn, которая создается из A путем удаления некоторых элементов, но с сохранением порядка. Для заданной целочисленной последовательности A цель состоит в том, чтобы вычислить b чередующейся подпоследовательности B, т. е. последовательности b1, ... bn такой, что для всех i из {2, 3, ..., m-1}, если b{i- 1} ‹ b{i}, тогда b{i} > b{i+1} и если b{i-1} > b{i}, то b{i} ‹ b{i+1}
До сих пор мне нужно проверять каждый рекурсивный шаг, хочу ли я взять элемент и искать следующее чередующееся число, или если я просто возьму следующее число и начну с обоих возможных чередований.
s индекс слева e конец ( len(Array)) Массив g(A,s) функция, которая получает следующее большее или меньшее целое число.
моя рекурсивная формула: V(A, s, e) = max( V(A, g(A,s),e), V(A, s+1, e)) +1
V(A, g(A,s),e) берет элемент и переходит к следующему чередующемуся элементу
V(A, s+1, e) покидает элемент и начинает новую последовательность со следующего элемента
предполагая, что моя реализация и подход верны, я предлагаю время выполнения O (n ^ 2), поскольку нам нужно знать каждую комбинацию.
Без части месмеризации это было бы O (2 ^ n), как количество листьев бинарных деревьев.
Верен ли этот анализ? Возможно, это правильно для формулы, но не для кода...
функции getsmaller и getbigger равны g(A,s)
A = [5,6,5,5,5,7,5,5,5,87,5]
s = 0
e = len(A)
memo_want_small = [-1] * len(A)
memo_want_bigger = [-1] * len(A)
def getsmaller(A, s):
erg = 0
for i in range(s, len(A)):
if A[i] < A[s]:
if i is not None:
return i
return -1
def getbigger(A, s):
for i in range(s, len(A)):
if A[i] > A[s]:
if i is not None:
return i
return -1
def wantsmall(A, s, e):
if s == -1: # no more alternating element
return 0
if s == e: # base case
return 0
if memo_want_small[s] is not -1:
return memo_want_small[s]
return_V = max(wantbigger(A, getbigger(A, s), e) , alt(A, s+1, e)) + 1
memo_want_small[s] = return_V
return return_V
def wantbigger(A, s, e):
if s == -1: # no more alternating element
return 0
if s == e: # base case
return 0
if memo_want_bigger[s] is not -1:
return memo_want_bigger[s]
return_V = max(wantsmall(A, getsmaller(A, s), e) , alt(A, s+1, e)) + 1
memo_want_bigger[s] = return_V
return return_V
def alt(A, s, e):
if s == e: # base case
return 0
return max(wantsmall(A, getsmaller(A, s), e), wantbigger(A, getbigger(A, s), e))
print("solution: " + str(alt(A,s,e)))
