Недостаток рекурсивного решения в том, что одинаковые подзадачи вызываются много раз в разное время.
Подзадача состоит в вызове lcs_length с суффиксами A и B в качестве аргументов, так что есть всего (m+1)(n+1) возможных подзадач. Это - весьма маленькое число. При ~2n рекурсивных вызовах некоторые из них будут решаться много раз заново.
Решение, использующее динамическое программирование, состоит в проверке, в каком случае нам нужно решать подзадачу, а в каком - она уже решена. Тогда мы просто посмотрим вверх, на предыдущее решение, не вычисляя его еще раз.
Делая это 'в лоб', мы просто добавим в наш рекурсивный алгоритм код, который будет смотреть вверх. Такая рекурсивная версия динамического программирования - 'сверху вниз' называется запоминанием.
Подзадачи состоят из двух суффиксов наших строк. Чтобы хранить и заглядывать в решения подзадач было легче, будем представлять их начальными позициями в строках, а не указателями на символы (как было раньше).
char * A;
char * B;
int lcs_length(char * AA, char * BB)
{
A = AA; B = BB;
return subproblem(0, 0);
}
int subproblem(int i, int j)
{
if (A[i] == '\0' || B[j] == '\0') return 0;
else if (A[i+1] == B[j+1]) return 1 + lcs_length(i+1, j+1);
else return max(lcs_length(i+1, j), lcs_length(i, j+1));
}
Теперь, для превращения этого в алгоритм динамического программирования, нам нужно всего лишь использовать массив для хранения решений подзадач.
Когда нам понадобится решение подзадачи, мы первым делом заглядываем в массив и проверяем, есть ли оно там. Если да - возвращаем его. Нет - вычисляем и сохраняем результат.
У подзадач не может быть отрицательных результатов, поэтому -1 будет флагом, говорящим, что еще ничего не вычислено.
char * A;
char * B;
array L;
int lcs_length(char * AA, char * BB)
{
A = AA; B = BB;
allocate storage for L;
for (i = 0; i <= m; i++)
for (j = 0; j <= m; j++)
L[i,j] = -1;
return subproblem(0, 0);
}
int subproblem(int i, int j)
{
if (L[i,j] < 0) {
if (A[i] == '\0' || B[j] == '\0') L[i,j] = 0;
else if (A[i+1] == B[j+1]) L[i,j] = 1 + lcs_length(i+1, j+1);
else L[i,j] = max(lcs_length(i+1, j), lcs_length(i, j+1));
}
return L[i,j];
}
Каждый вызов подзадачи требует константного времени. Мы делаем его один раз из главной процедуры и, самое большее, два раза каждый раз заполняя пустоты в массиве L.
Там есть всего (m+1)(n+1) пустых мест, поэтому количество вызовов - не более 2(m+1)(n+1)+1, а, значит, время в худшем случае - O(mn).
8 8 8
| |
*
Обратная связь