Решение динамического программирования для «размагничивания» двух последовательностей

Question

У меня есть проблема, которую я пытаюсь решить, но мне очень не повезло. Вот проблема:

«Если две последовательности a1, a2, ..., am и b1, b2, ..., bn чередуются, мы говорим, что результирующая последовательность c1, c2, ..., cm + N является перетасовка первых двух, например,

DCCDBDADCACDBACB

является перетасовка DCBDAACBB и CDDCDAC, поскольку она может быть получена путем чередования этих двух последовательностей таким образом:.

DC   BDA   AC   B    B 

     CD    DC   D   AC" 

Я должен найти решение динамического программирования, которое определяет, являются ли две заданные подпоследовательности abl e для объединения в большую последовательность. Я уже сделал проблему с поиском самой длинной общей подсекции и такой, но я не могу представить ее. Я знаю, как это сделать, если я не буду рассматривать динамическое программирование, но я не могу представить, как это сделать с ним.

Любая помощь была бы принята с благодарностью.

Спасибо!

Answer 1

Вы можете построить алгоритм DP для решения этого, но первое создание рекурсивного решения, например:

a = 'DCBDAACBB' 
b = 'CDDCDAC' 
c = 'DCCDBDADCACDBACB' 

an = len(a) 
bn = len(b) 
cn = len(c) 


# recursive solution O(2^n) 
def isPossible(ai, bi, ci): 

    if ai == an and bi == bn and ci == cn: 
     return True 

    K = False 

    if ci < cn and ai < an and c[ci] == a[ai]: 
     K = K or isPossible(ai+1, bi, ci+1) 

    if ci < cn and bi < bn and c[ci] == b[bi]: 
     K = K or isPossible(ai, bi+1, ci+1) 

    return K 

print isPossible(0, 0, 0) 

Здесь государство может быть закодирована в виде трех чисел ai, bi, ci которые указывают индекс начала суффикса исходные строки и isPossible(ai, bi, ci) вычисляют, могут ли суффиксы ai и bi быть объединены в суффикс ci, мы ищем isPossible(0, 0, 0).

Отсюда мы можем создать следующий DP рецидивы, первая инициализация:

isPossible[ai][bi][ci] = False 
isPossible[ai][bi][ci] = True where ai == an and bi == bn and ci == cn 

Затем вычисляем:

isPossible[ai][bi][ci] = isPossible[ai+1][bi][ci+1] if A[ai] == C[ai] 
isPossible[ai][bi][ci] = isPossible[ai][bi+1][ci+1] if B[ai] == C[ai] 

Раствор затем isPossible[0][0][0]. Это выполняется в n^3, где в качестве рекурсивного решения 2^n