Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Поиск в строках, массивах, последовательностях / Общие подпоследовательности. Дистанция / Задача о наибольшей общей подпоследовательности. /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Динамическое программирование снизу вверх - Программирование от RIN.RU
Динамическое программирование снизу вверх

То, что было описано выше - всего лишь более умный путь создания рекурсивного алгоритма. Но можно считать эту программу способом заполнения массива L. Последовательность заполнения контролирует рекурсия, однако те же результаты можно получить и при другом порядке.


Мы можем придумать что-нибудь попроще, что будкт этим заниматься. Единственная проблема - для заполнения L[i,j] нам нужно знать то, от чего зависит его значение: в данном случае, это L[i+1,j], L[i,j+1] и L[i+1,j+1].


А потому - будем идти по массиву назад, от последнего ряда к первому, и от последней колонке - вверх к первой. Наш алгоритм станет итерационным, используя циклы вместо рекурсии. Или алгоритмом снизу-вверх, так как мы будем заполнять массив от простых подзадач к более сложным.



 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Источник: http://www.krasnodar-live.ru.