В предыдущих двух статьях мы объяснили проблему рюкзака 01 и проблему минимальной сдачи монет. В этой статье будет представлена еще одна классическая задача динамического программирования — самая длинная общая подпоследовательность. Если вы не читали первые два, нажмите на ссылку ниже.
Подробное объяснение проблемы рюкзака с динамическим программированием 01 - реализация JavaScript
вопрос
abcadf , acbad
анализировать
Самая длинная общая проблема последовательности, следует отметить три момента
- Две последовательности не обязательно имеют одинаковую длину
- Самая длинная подпоследовательность — это та, которая встречается в одном и том же порядке в двух последовательностях строк.
- Желаемая подпоследовательность не обязательно должна быть непрерывной
Перед выполнением анализа заполнения формы, в соответствии с тремя пунктами, упомянутыми выше, мы можем легко получить ответ непосредственно сначала, самая длинная общая подпоследовательность должна бытьacad
Строительный стол
Мы предваряем обе подпоследовательности нулевым символом, т.е.
input1 = ["","a","c","b","a","d"],
input2 = ["","a","b","c","a","d","f"],
Затем постройте следующую таблицу
Зачем заполнять кучу нулей? Указывает, что строка не может быть сопоставлена.Вы можете понять, что это вспомогательный метод расчета.Не учитывать сконструированный нулевой символ при анализе конкретных подпоследовательностей. Сзади по идеям двух предыдущих статей использоватьT[i][j]Указывает общую длину подпоследовательности.
Следующие формы заполняются слева направо и сверху вниз. Когда мы заполняем определенную форму, нам нужно рассматривать только случаи меньше или равно i и меньше или равно j. Например, когда мы хотим заполнить T[2][2], это эквивалентно поиску строкиac,abСамая длинная общая подпоследовательность , заполните T[4][5], тогда это эквивалентно нахождениюacba,abcadСамая длинная общая длина подпоследовательности.
Если вы читали первые две статьи, то должны быть знакомы с этой формой заполнения. На основе этой формы начните заполнять форму ниже.
2. i =1
i=1 j=1aа такжеaСамая длинная общая длина подпоследовательности , очевидно, равна 1.
i=1 j=2: это эквивалентно поиску строкиaа такжеabСамая длинная общая длина подпоследовательности , результат равен 1.
i=1 j=3: это эквивалентно поиску строкиaа такжеabcСамая длинная общая длина подпоследовательности , результат равен 1.
Пока последовательность имеет только один символ, самая длинная общая подпоследовательность другой последовательности, независимо от ее длины, может иметь длину не более 1. Следовательно, оставшиеся пробелы в строке i=1 заполняются цифрой 1.
3. i = 2
i=2 j=1: это эквивалентно поиску строкиacа такжеaСамая длинная общая длина подпоследовательности , результат равен 1.
i=2 j=2: это эквивалентно поиску строкиacа такжеabСамая длинная общая длина подпоследовательности , результат равен 1.
i=2 j=3: это эквивалентно поиску строкиacа такжеabcНаибольшая общая длина подпоследовательности . Вот когда это становится интересным. Поскольку в соответствии с первоначальным анализом при обнаружении самой длинной распространенной подпоследовательности подпоследовательности могут быть прерывистыми, поэтому самая длинная распространенная подпоследовательность этих двух последовательностей должна бытьacТак вот таблица должна быть заполнена 2.
Ну стоп, не спешите продолжать заполнение, надо сначала проанализировать общую идею.
4. Идеи заполнения форм
Мы [2] [3] = 2 из этой сетки анализа T. Очевидно удалениеca, ab.是不是有点熟悉？这个其实就是填写 T[1][2] 时的组合，也就是我们可以假设当input1[i] == input2[j]час,T[i][j]=T[i-1][j-1]+1.
когдаinput1[i] != input2[j]час,T[i][j][i][j] = max(T[i-1][j],T[i][j-1]).
Опишите это простыми словамиT[i][j]правилоВерхний левый угол равен одному плюс один, а верхнее или левое максимальное значение не равно.Если верхний левый и верхний левый совпадают, левый предпочтительнее.
Ну, не смотрите на содержание следующего, вы принимаете этот закон, остальное содержание их собственных форм завершено.
5. Финальный стол
Понимая этот закон, нам не нужно повторять описание заполнения каждой графы. Ниже представлена окончательная форма.
Возьмем пример, такой как i=5 j=4, в это времяinput1[i] !=input2[j], мы берем большее значение слева (2) или выше (3), поэтому заполняем 3.
i=5 j=5, в это времяinput1[i] ==input2[j], мы напрямую берем значение верхнего левого угла и добавляем 1, а значение верхнего левого угла равно T[4][4]=3, поэтому T[5][5]=4.
Если вы все еще не понимаете этого, вы можете снова попрактиковаться в рисовании самостоятельно.
Согласно формуле для заполнения формы, предоставленной ранее, мы можем изменить формулу для поиска подпоследовательностей:Подпоследовательность, если T[i][j] исходит из верхнего левого угла плюс один, в противном случае откат влево или вверх. Если верхний левый имеет одинаковый размер, левый предпочтительнее.
1.Начинайте анализ с правого нижнего угла, T[5][6]=4, а не с левого верхнего угла. Значение слева от него больше, чем значение сверху, поэтому оно исходит слева и возвращается влево, как показано стрелкой на рисунке ниже.
2.Затем он находит T [5] [5], что, очевидно, происходит из верхнего левого угла плюс 1, что является подпоследовательностью. Вставить в массив, есть
s = ['d']
3.Вычтите T [5] [5], вы можете найти его верхний левый угол T [4] [4], как показано на рисунке:
T[4][4] также из левого верхнего угла плюс 1, это тоже подпоследовательность, вставьте ее в начало массива, в это время s должно быть
s = ['a','d']
4.Согласно предыдущим идеям, продолжаем анализ позиционирования и, наконец, следующий рисунок:
s = ['a','b','a','d']
Поддельный код
Весь процесс анализа завершен. Логика кода представлена ниже.Даже если вы не понимаете JavaScript, это не повлияет на ваше понимание, потому что здесь не задействована языковая особенность.
заполнить форму
if(input1[i] == input2[j]){
T[i][j] = T[i-1][j-1] + 1;
}else{
T[i][j] = max(T[i-1][j],T[i][j-1])
}
Выглядящая подстрока
if(input1[i] == input2[j]){
s.insertToIndexZero(input1[i]); //插入到数组最前面
i--;
j--;
}else{
//向左或向上回退
if(T[i-1][j]>T[i][j-1]){
//向上回退
i--;
}else{
//向左回退
j--;
}
}
полный код
Окончательный код реализован на JavaScript.Если ваш Sublime поддерживает чистый JavaScript, вы можете напрямую скопировать и вставить код, выполнить команду + b напрямую, чтобы просмотреть результаты, а затем изменить входные переменные, чтобы просмотреть выходные результаты в большем количестве случаев.
//动态规划 -- 最长公共子序列
//!!!! T[i][j] 计算，记住口诀：相等左上角加一，不等取上或左最大值
function longestSeq(input1,input2,n1,n2){
var T = []; // T[i][j]表示 公共子序列长度
for(let i=0;i<n1;i++){
T[i] = [];
for(let j= 0;j<n2;j++){
if(j==0 ||i==0){
T[i][j] = 0;
continue;
}
if(input1[i] == input2[j]){
T[i][j] = T[i-1][j-1] + 1;
}else{
T[i][j] = Math.max(T[i-1][j],T[i][j-1])
}
}
}
findValue(input1,input2,n1,n2,T);
return T;
}
//!!!如果它来自左上角加一，则是子序列，否则向左或上回退。
//findValue过程，其实就是和 就是把T[i][j]的计算反过来。
function findValue(input1,input2,n1,n2,T){
var i = n1-1,j=n2-1;
var result = [];//结果保存在数组中
console.log(i);
console.log(j);
while(i>0 && j>0){
if(input1[i] == input2[j]){
result.unshift(input1[i]);
i--;
j--;
}else{
//向左或向上回退
if(T[i-1][j]>T[i][j-1]){
//向上回退
i--;
}else{
//向左回退
j--;
}
}
}
console.log(result);
}
//两个序列，长度不一定相等, 从计算表格考虑，把input1和input2首位都补一个用于占位的空字符串
var input2 = ["","a","b","c","a","d","f"],
input1 = ["","a","c","b","a","d"],
n1 = input1.length,
n2 = input2.length;
console.log(longestSeq(input1,input2,n1,n2));