Один из недостатков описанного метода динамического программирования, по сравнению с исходной рекурсией - в том, что он требует O(mn) памяти на массив L ( рекурсия - O(n+m) ). Но итерационная версия вполне может быть подредактирована, чтобы использовать меньше пространства: после вычисления i-го ряда нам уже не нужны значения в ряду i+1. Не требовательное к памяти LCS: int lcs_length(char * A, char * B) { allocate storage for one-dimensional arrays X and Y for (i = m; i >= 0; i--) { for (j = n; j >= 0; j--) { if (A[i] == '\0' || B[j] == '\0') X[j] = 0; else if (A[i+1] == B[j+1]) X[j] = 1 + Y[j+1]; else X[j] = max(Y[j], X[j+1]); } Y = X; } return X[0]; } Временные затраты примерно такие же ( + небольшая константа ), однако памяти нужно лишь O(m) или O(n) - что меньше ( меняем их местами, если надо, чтобы рядов было больше, чем столбцов). Но такое решение даст нам лишь длину подпоследовательности, стирая остнформацию.  8  Комментарии к статье  8 8  Обсудить в чате