@Frommi2 сен 2013 в 18:21

Всё, что вы хотели знать о динамическом программировании, но боялись спросить

12 мин

254K

Алгоритмы *

+89

Комментарии 33

@HomoLuden 2 сен 2013 в 18:34

dmytry.com/games/try_polynomial.html
Вот это я понимаю динамическое программирование… а вы тут цихерки какие-то…

Шутка, конечно. Я и сам тащусь от данимических систем. Спасибо за статью.

@AndrewShmig 2 сен 2013 в 18:37

OMG!
Статью бы хоть прочли или в вики глянули.

@HomoLuden 2 сен 2013 в 19:09

«Чтобы успешно решить задачу динамикой нужно:
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.»

1: Значение фазовых переменных системы дифференциальных уравнений в частных производных
2: То же для фазовых переменных
3: Коэффициенты при частных производных
4: Порядок следования уравнений в системе
5: Кодирование цвета и яркости точек текущим решением системы

Пусть приложено ДП к другой задаче, но сути динамических систем это не меняет.

@HomoLuden 2 сен 2013 в 19:46

Знай что ревностно мы бдим.
Знаний наши непорочных
Честь в обиду не дадим
Вот таким как ты, побочным.

За обиду на под-дых!
И в глазницу на вдогонку!
За деревья и гнедых
В карму плюнем мы подонку!

Спасибо за вдохновение :)

@xtender 2 сен 2013 в 20:39

Формат мне понравился. Не то, что алголист :) Но все-таки тем формат и наполнение алголиста при системном подходе лучше

@kosiakk 2 сен 2013 в 22:40

Рекомендую обратить внимание на язык динамического программирования Dyna.
Вторая версия (в разработке) на выходе даже выдаёт код на Пайтоне по декларативному описанию задачи.

@naething 3 сен 2013 в 02:41

Надо только добавить, что «программирование» здесь — синоним слова «оптимизация» (то есть как «линейное программирование», а не «функциональное программирование»).

@DmitriyH 3 сен 2013 в 07:50

Спасибо, очень познавательная статья, все разложено по полочкам!
Реквестирую в таком же ключе статью про подраздел динамики «Convex Hull Trick» :)

@Frommi 3 сен 2013 в 11:32

До Вашего комментария я ни разу не слышал про этот интересный подраздел, так что если я и напишу статью, то только когда почитаю побольше и порешаю какие-нибудь задачки на него. Вроде здесь неплохо написано, но на английском. На русском ничего нашёл, так что вероятность того, что я напишу что-нибудь есть.

@DmitriyH 3 сен 2013 в 11:57

Англоязычную статью по ссылке я читал, но осталось много вопросов. Прочитав статью, я по-прежнему не смог придумать решение для известных мне задач на эту тематику (первая и вторая).

@Snowbear 4 сен 2013 в 14:14

Из собственного опыта — Convex Hull Trick стоит начать с того примера, который в англоязычной статье и указан — задача USACO MAR08. Там довольно подробно вывод идет и насколько я помню, там не очень много кода, отвлекающего от собственно Convex Hull Trick. Прочитав статью и примерно с пятого раза написав решение к задаче из статьи, «Транспортировку кошек» уже смог решить сам. Если, конечно, можно сказать «сам», когда тебе подсказали каким приемом надо воспользоваться.

@Bangybug 3 сен 2013 в 08:48

3) Формулы пересчёта: есть по восемь букв, использующих одно, два и три нажатия соответственно, а так же две буквы за 4 нажатия.

* есть восемь кнопок, на которых разные буквы можно набрать за одно, два и три нажатия
* на двух из этих же кнопок, есть две буквы, которые набираются за 4 нажатия

@Bangybug 3 сен 2013 в 09:05

Это я прицепился к неточности, как мне показалось. На самом деле, я не сразу сообразил, что речь шла о разнице между предыдущим и следующим состоянием.

@Frommi 3 сен 2013 в 11:55

Немного переписал это предложение, вроде стало читабельней, но всё-таки лучше такие комментарии писать в личку автора.

@spiff 3 сен 2013 в 12:07

Спасибо за статью.

Извиняюсь за твердолобость, но можно ссылку на почитать про товарища А. Кумок. Уж больно цитата в начале статьи понравилась.

@Frommi 3 сен 2013 в 12:25

Аким Кумок скорее всего произнёс эту фразу, когда был преподавателем в Летней Компьютерной Школе. Особо много видимо про него не почитать, но я знаю, что он получил серебро на международной олимпиаде по информатике среди школьников в 2008 году.

НЛО прилетело и опубликовало эту надпись здесь

@Frommi 3 сен 2013 в 17:23

Да, это самый универсальный способ, но есть пара тонкостей. Во-первых, она практически всегда требует больше памяти и времени на вызов рекурсивной функции. Во-вторых, не получится оптимизировать память, забывая про предыдущие «слои» состояний. Про это написано в «Небольшие оптимизации».

@Nashev 3 сен 2013 в 18:01

Я правильно понимаю, что «динамическое программирование» — это «лишь» один из видов применения понятия «рекурсия»?
Ну, то есть что всё программы, полученные посредством динамического программирования рекурсивны, но не все рекурсивные программы можно отнести к динамическому программированию?

@Frommi 3 сен 2013 в 18:12

Любая динамика определяется рекурсивно — без этого нельзя свести задачу к меньшим подзадачам. Если Вы имели в виду это, то да, но реализация рекурсивной функцией обязательна только если порядок обхода был ленивым.

@Nashev 3 сен 2013 в 18:36

И эта задача обязательно должна быть подобна тем меньшим задачам, на которые её разбивают, и соответственно, они тоже должны мочь разбиваться на самоподобные задачи меньшей мощности (ну, вплоть до граничных случаев). То бишь, по сути — задача должна быть фрактальна! Да?

@Frommi 3 сен 2013 в 19:00

В принципе да, хотя слово «фрактал», на мой взгляд, тут не самое уместное. А ещё бывают всякие интересные случаи, например, когда одна задача решается с помощью значений состояний другой задачи, которая в свою очередь, основывается на значениях первой — такая запутанная динамика. Сейчас уже пример не вспомню, но такое действительно иногда встречается.

@Nashev 3 сен 2013 в 19:27

К некоторым таким запутанным случаям можно и голографию приплести, будет вполне уместно… Аналогии — они такие аналогии!

Спасибо!

@spiff 4 сен 2013 в 15:09

Небольшая поправочка к первому примеру. Ответ будет не сумма *всех* состояний а сумма состояний при (j == k) т.е. сумма последнего столбца в матрице dp. По условию dp[i][j] содержит количество сообщений длины i, которые можно напечатать используя не больше j нажатий. Т.е. нас интересует только последний столбец, т.к. он и содержит ответы.

Как то сумбурно написал, но надеюсь понятно.

Вот код

// Problem 1 (DP)
  // O(k^2)
  public static int smsDP(int k) {
    // base case
    if (k == 0) return 1;

    // dp[i][j] - is a number of messages
    // that with length 'i' that uses 'j' presses
    int dp[][] = new int[k + 1][k + 1];

    // initial state
    // we can write only one message (an empty with length 0) by zero presses
    //for (int i = 0; i < k; i++) {
      dp[0][0] = 1;
    //}

    // answer
    int result = 0;

    // fill the dp
    // we can't write message with length M by pressing N keys, where M > N
    // this is why we're trying to get an upper triangular matrix
    for (int i = 1; i < k + 1; i++) {
      for (int j = i; j < k + 1; j++) {
        dp[i][j] = dp[i - 1][j - 1] * 8;
        if (j - 1 > 0) {
          dp[i][j] += dp[i - 1][j - 2] * 8;
        }
        if (j - 2 > 0) {
          dp[i][j] += dp[i - 1][j - 3] * 8;
        }
        if (j - 3 > 0) {
          dp[i][j] += dp[i - 1][j - 4] * 2;
        }

        if (j == k) {
          result += dp[i][j];
        }
      }
    }

    return result;
  }

@spiff 4 сен 2013 в 15:29

Кажется я запутался. Правильно ли я понимаю, что наивная (без ДП) реализация для первой задачи выглядит вот так:

// Problem 1 (Naive)
  // O(4^k)
  public static int smsNaive(int k) {
    if (k < 0) return 0;
    if (k == 0) return 1;
    return  8 * smsNaive(k - 1) + 
            8 * smsNaive(k - 2) + 
            8 * smsNaive(k - 3) + 
            2 * smsNaive(k - 4);
  }

@Frommi 4 сен 2013 в 16:16

Да, но ответ на задачу теперь получается так:

public static int getAns() {
    int result = 0;
    for (int i = 0; i < k + 1; i++) {
        result += smsNaive(i);
    }
    return result;
}

@Frommi 4 сен 2013 в 16:21

Не путайте условие и состояние динамики. Состояние не обязательно должно быть прямо ответом на задачу — в моем состоянии это сообщения ровно за j нажатий, так что ответ будет суммой всех состояний. Если бы состояние было такое, как Вы описали — «не больше j нажатий», то такой (как в статье) пересчёт бы не работал, ведь тогда бы мы посчитали некоторые сообщения несколько раз.
Как написали ниже, я решил задачу не оптимально, можно и одномерно решить.

@spiff 4 сен 2013 в 16:33

Да. Теперь разобрался. Спасибо!

Код решения (Наивное и Динамика)

// Problem 1 (Naive)
  // O(k^k)
  public static int smsNaive(int k) {
    int result = 0;
    for (int i = 1; i < k + 1; i++) {
      result += smsNaiveHelper(i);
    }
    return result;
  }

  public static int smsNaiveHelper(int k) {
    if (k < 0) return 0;
    if (k == 0) return 1;
    return 8 * smsNaiveHelper(k - 1) + 
           8 * smsNaiveHelper(k - 2) + 
           8 * smsNaiveHelper(k - 3) + 
           2 * smsNaiveHelper(k - 4);
  }

  // Problem 1 (DP)
  // O(k^2)
  public static int smsDP(int k) {
    // dp[i] - is a number of messages
    // that uses 'i' presses
    int dp[] = new int[k + 1];

    // initial state
    // we can write only one message (an empty with length 0) by zero presses
    dp[0] = 1;

    // result
    int result = 0;

    // fill the dp
    for (int i = 1; i < k + 1; i++) {
      dp[i] += dp[i - 1] * 8;
      if (i - 1 > 0) {
        dp[i] += dp[i - 2] * 8;
      }
      if (i - 2 > 0) {
        dp[i] += dp[i - 3] * 8;
      }
      if (i - 3 > 0) {
        dp[i] += dp[i - 4] * 2;
      }

      result += dp[i];
    }

    return result;
  }