Динамическое программирование. Введение.

от
Прочее
Сегодня я хочу вам рассказать об идее(вернее, группе идей), весьма широко использующейся в программировании. Имя ей - динамическое программирование.

     Что вообще представляет из себя эта идея? По википедии - это
способ решения сложных задач путём разбиения их на более простые подзадачи.     Или
Динамическое программирование - это когда у нас
есть одна большая задача, которую непонятно как решать,
и мы разбиваем ее на меньшие задачи, которые тоже
непонятно как решать.
     Рассмотрим эту идею на примере. Решим задачу:
Назовём число интересным, если цифры в нём идут в порядке неубывания. Так, числа 123 или 448899 являются интересными, а число 123452 - нет. Посчитайте количество интересных чисел на отрезке
  Попытка №1     Первое, что приходит в голову - давайте переберём все числа данного промежутка и проверим каждое на интересность. OK, пишем код:
  1. long long countinteresting(long long l, long long r)
  2. {
  3.     long long cnt = 0;
  4.     for(long long currnumber = l; currnumber <= r; ++currnumber)
  5.     {
  6.         bool isnotdescending = true;
  7.         int prevdigit = 0, currdigit = 0;
  8.         long long tmp = currnumber;
  9.         long long power = 1; // Наибольшая степень десятки, не большая нашего числа
  10.         while(power<=tmp) power *= 10;
  11.         power /= 10;
  12.         while(power&&isnotdescending)
  13.         {
  14.             prevdigit = currdigit;
  15.             currdigit = tmp/power;
  16.             if(currdigit<prevdigit) isnotdescending = false;
  17.             else
  18.             {
  19.                 tmp %= power;
  20.                 power /= 10;
  21.             }
  22.         }
  23.         if(isnotdescending) ++cnt;
  24.     }
  25.     return cnt;
  26. }

     Однако, сколько будет работать такое решение? Проще всего это подсчитать для границ 1 и 10^k. У нас получится:


     Не очень-то быстро, не правда ли? Уже для k = 25 последнее слагаемое равно 25*9*10^24, т. е. подсчёт только чисел длины k будет производиться 25*9*10^13 секунд или 71347031 лет. Хотя казалось бы, 10^25 - не такое уж большое число. Окей, нам нужно решение быстрей.

     Попытка №2     На минуту забудем про остальные варианты и будем считать что , а . Давайте насчитаем такую табличку: , где будем хранить количество чисел длины j, начинающихся на i. Как её заполнять? Очевидно, , ведь есть ровно одно число, состоящее из одной цифры и начинающееся с неё - сама эта цифра.

     С базой разобрались, но как перейти от j к j+1? К каким числам мы можем приписать спереди цифру i так, чтобы они остались интересными? Конечно же тем, которые начинаются с цифр, не меньших, чем i. Таким образом, получаем, что

Заметим, что для получения ответа нам достаточно просуммировать , где j пробегает значения от 1 до (k+1).
     Код решения:
  1. long long countinteresting(long long length)
  2. {
  3.     vector<vector<int>> table(length+1, vector<int>(10, 1));
  4.     long long answer = 0;
  5.     for(long long j = 1; j<=length; ++j)
  6.     {
  7.         long long sum = 0;
  8.         for(int i = 9; i>=1; --i)
  9.         {
  10.             sum += table[j-1][i];
  11.             table[j][i] = sum;
  12.         }
  13.         answer += table[j][1];
  14.     }
  15.     return answer;
  16. }
     Посчитаем сложность этого решения. Легко видеть, она равна 10*(k+1).
    Уже лучше, но мы всё ещё не умеем находить ответ для любых l и r. Поэтому

    Попытка №3 и полное решение     К сожалению, такое пока писать не научился, поэтому кода тут не будет. Суть идеи останется прежней, только теперь мы будем перебирать длину общего префикса(первые цифры) для интересного числа и r и смотреть, сколько чисел с таким префиксом таких, что следующая цифра строго меньше соответствующей цифры из r. Пересчитывается таблица так же, меняются только начальные значения.

     Теперь, когда мы умеем для любого n находить количество интересных чисел от 1 до n, понятно, как найти ответ для отрезка : посчитаем ответ для r и для (l-1). Разница и будет искомым ответом.

    В заключение    В этой статье я попытался дать общее представление об идее под названием динамическое программирование и показать его использование на сферическом примере в вакууме. В следующий раз попробую дать классификацию методов ДП и более практические задачи с его использованием.
Прочее
Категории