Как стать автором
Обновить

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

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

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

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

Пусть приложено ДП к другой задаче, но сути динамических систем это не меняет.
Знай что ревностно мы бдим.
Знаний наши непорочных
Честь в обиду не дадим
Вот таким как ты, побочным.

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

Спасибо за вдохновение :)
Формат мне понравился. Не то, что алголист :) Но все-таки тем формат и наполнение алголиста при системном подходе лучше
Рекомендую обратить внимание на язык динамического программирования Dyna.
Вторая версия (в разработке) на выходе даже выдаёт код на Пайтоне по декларативному описанию задачи.
Надо только добавить, что «программирование» здесь — синоним слова «оптимизация» (то есть как «линейное программирование», а не «функциональное программирование»).
Спасибо, очень познавательная статья, все разложено по полочкам!
Реквестирую в таком же ключе статью про подраздел динамики «Convex Hull Trick» :)
До Вашего комментария я ни разу не слышал про этот интересный подраздел, так что если я и напишу статью, то только когда почитаю побольше и порешаю какие-нибудь задачки на него. Вроде здесь неплохо написано, но на английском. На русском ничего нашёл, так что вероятность того, что я напишу что-нибудь есть.
Англоязычную статью по ссылке я читал, но осталось много вопросов. Прочитав статью, я по-прежнему не смог придумать решение для известных мне задач на эту тематику (первая и вторая).
Из собственного опыта — Convex Hull Trick стоит начать с того примера, который в англоязычной статье и указан — задача USACO MAR08. Там довольно подробно вывод идет и насколько я помню, там не очень много кода, отвлекающего от собственно Convex Hull Trick. Прочитав статью и примерно с пятого раза написав решение к задаче из статьи, «Транспортировку кошек» уже смог решить сам. Если, конечно, можно сказать «сам», когда тебе подсказали каким приемом надо воспользоваться.
3) Формулы пересчёта: есть по восемь букв, использующих одно, два и три нажатия соответственно, а так же две буквы за 4 нажатия.

* есть восемь кнопок, на которых разные буквы можно набрать за одно, два и три нажатия
* на двух из этих же кнопок, есть две буквы, которые набираются за 4 нажатия
Это я прицепился к неточности, как мне показалось. На самом деле, я не сразу сообразил, что речь шла о разнице между предыдущим и следующим состоянием.
Немного переписал это предложение, вроде стало читабельней, но всё-таки лучше такие комментарии писать в личку автора.
Спасибо за статью.

Извиняюсь за твердолобость, но можно ссылку на почитать про товарища А. Кумок. Уж больно цитата в начале статьи понравилась.
Аким Кумок скорее всего произнёс эту фразу, когда был преподавателем в Летней Компьютерной Школе. Особо много видимо про него не почитать, но я знаю, что он получил серебро на международной олимпиаде по информатике среди школьников в 2008 году.
НЛО прилетело и опубликовало эту надпись здесь
Да, это самый универсальный способ, но есть пара тонкостей. Во-первых, она практически всегда требует больше памяти и времени на вызов рекурсивной функции. Во-вторых, не получится оптимизировать память, забывая про предыдущие «слои» состояний. Про это написано в «Небольшие оптимизации».
Я правильно понимаю, что «динамическое программирование» — это «лишь» один из видов применения понятия «рекурсия»?
Ну, то есть что всё программы, полученные посредством динамического программирования рекурсивны, но не все рекурсивные программы можно отнести к динамическому программированию?
Любая динамика определяется рекурсивно — без этого нельзя свести задачу к меньшим подзадачам. Если Вы имели в виду это, то да, но реализация рекурсивной функцией обязательна только если порядок обхода был ленивым.
И эта задача обязательно должна быть подобна тем меньшим задачам, на которые её разбивают, и соответственно, они тоже должны мочь разбиваться на самоподобные задачи меньшей мощности (ну, вплоть до граничных случаев). То бишь, по сути — задача должна быть фрактальна! Да?
В принципе да, хотя слово «фрактал», на мой взгляд, тут не самое уместное. А ещё бывают всякие интересные случаи, например, когда одна задача решается с помощью значений состояний другой задачи, которая в свою очередь, основывается на значениях первой — такая запутанная динамика. Сейчас уже пример не вспомню, но такое действительно иногда встречается.
К некоторым таким запутанным случаям можно и голографию приплести, будет вполне уместно… Аналогии — они такие аналогии!

Спасибо!
Небольшая поправочка к первому примеру. Ответ будет не сумма *всех* состояний а сумма состояний при (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;
  }



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

// 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);
  }
Да, но ответ на задачу теперь получается так:

public static int getAns() {
    int result = 0;
    for (int i = 0; i < k + 1; i++) {
        result += smsNaive(i);
    }
    return result;
}
Не путайте условие и состояние динамики. Состояние не обязательно должно быть прямо ответом на задачу — в моем состоянии это сообщения ровно за j нажатий, так что ответ будет суммой всех состояний. Если бы состояние было такое, как Вы описали — «не больше j нажатий», то такой (как в статье) пересчёт бы не работал, ведь тогда бы мы посчитали некоторые сообщения несколько раз.
Как написали ниже, я решил задачу не оптимально, можно и одномерно решить.
Да. Теперь разобрался. Спасибо!

Код решения (Наивное и Динамика)
// 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;
  }



А для задачи с СМСками правда требуется многомерная динамика? Просто пройтись циклом по количеству нажатий недостаточно?
Да, действительно, что-то я жутко ступил. Мне показалось, что тогда некоторые сообщения будут посчитаны несколько раз…
Достаточно странное и неверное определение ДП.

Ленивая динамика, так же, ненужный и не ясный термин
НЛО прилетело и опубликовало эту надпись здесь

Написал в продолжение этой статьи со ссылкой на нее

Как найти возможные суммы из N элементов в массиве

https://habr.com/ru/post/599439/

Огромное спасибо автору

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.