У меня возникли проблемы с построением этого отношения повторения.
У нас есть три струны:
x=x1x2x3....xn
y=y1y2y3....ym
z=z1z2z3....zm
Проблема состоит в том, чтобы найти длину самой длинной последовательности, которая является подпоследовательностью всех трех последовательностей.
Построенное мной повторение выглядит так:
T(i,j,k)= O(1) if i=0 or j=0 or k=0
T(i-1,j-1,k-1) if (x[i]==y[j]==z[k])
max(T(i-1,j,k)+T(i,j-1,k)
+T(i,j,k-1)) otherwise
where i is the length of x
j is the length of y
k is the length of z
Мне было интересно, правильно ли это, поскольку я не уверен, можем ли мы использовать if (x [i] == y [j] == z [k]) в качестве случая





Таким условием, безусловно, является позволил (почему вы думаете, что это не так?), Хотя для проверки правильности вашего общего повторения вам следует просмотреть пример и убедиться, что он возвращает правильный результат. Хотя big-O здесь не место, при условии, что вы пытаетесь получить длину, а не то, сколько времени потребуется, чтобы получить длину.