Comments 33
dmytry.com/games/try_polynomial.html
Вот это я понимаю динамическое программирование… а вы тут цихерки какие-то…
Шутка, конечно. Я и сам тащусь от данимических систем. Спасибо за статью.
Вот это я понимаю динамическое программирование… а вы тут цихерки какие-то…
Шутка, конечно. Я и сам тащусь от данимических систем. Спасибо за статью.
OMG!
Статью бы хоть прочли или в вики глянули.
Статью бы хоть прочли или в вики глянули.
«Чтобы успешно решить задачу динамикой нужно:
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.»
1: Значение фазовых переменных системы дифференциальных уравнений в частных производных
2: То же для фазовых переменных
3: Коэффициенты при частных производных
4: Порядок следования уравнений в системе
5: Кодирование цвета и яркости точек текущим решением системы
Пусть приложено ДП к другой задаче, но сути динамических систем это не меняет.
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.»
1: Значение фазовых переменных системы дифференциальных уравнений в частных производных
2: То же для фазовых переменных
3: Коэффициенты при частных производных
4: Порядок следования уравнений в системе
5: Кодирование цвета и яркости точек текущим решением системы
Пусть приложено ДП к другой задаче, но сути динамических систем это не меняет.
Формат мне понравился. Не то, что алголист :) Но все-таки тем формат и наполнение алголиста при системном подходе лучше
Рекомендую обратить внимание на язык динамического программирования Dyna.
Вторая версия (в разработке) на выходе даже выдаёт код на Пайтоне по декларативному описанию задачи.
Вторая версия (в разработке) на выходе даже выдаёт код на Пайтоне по декларативному описанию задачи.
Надо только добавить, что «программирование» здесь — синоним слова «оптимизация» (то есть как «линейное программирование», а не «функциональное программирование»).
Спасибо, очень познавательная статья, все разложено по полочкам!
Реквестирую в таком же ключе статью про подраздел динамики «Convex Hull Trick» :)
Реквестирую в таком же ключе статью про подраздел динамики «Convex Hull Trick» :)
До Вашего комментария я ни разу не слышал про этот интересный подраздел, так что если я и напишу статью, то только когда почитаю побольше и порешаю какие-нибудь задачки на него. Вроде здесь неплохо написано, но на английском. На русском ничего нашёл, так что вероятность того, что я напишу что-нибудь есть.
Из собственного опыта — Convex Hull Trick стоит начать с того примера, который в англоязычной статье и указан — задача USACO MAR08. Там довольно подробно вывод идет и насколько я помню, там не очень много кода, отвлекающего от собственно Convex Hull Trick. Прочитав статью и примерно с пятого раза написав решение к задаче из статьи, «Транспортировку кошек» уже смог решить сам. Если, конечно, можно сказать «сам», когда тебе подсказали каким приемом надо воспользоваться.
3) Формулы пересчёта: есть по восемь букв, использующих одно, два и три нажатия соответственно, а так же две буквы за 4 нажатия.
* есть восемь кнопок, на которых разные буквы можно набрать за одно, два и три нажатия
* на двух из этих же кнопок, есть две буквы, которые набираются за 4 нажатия
Спасибо за статью.
Извиняюсь за твердолобость, но можно ссылку на почитать про товарища А. Кумок. Уж больно цитата в начале статьи понравилась.
Извиняюсь за твердолобость, но можно ссылку на почитать про товарища А. Кумок. Уж больно цитата в начале статьи понравилась.
Аким Кумок скорее всего произнёс эту фразу, когда был преподавателем в Летней Компьютерной Школе. Особо много видимо про него не почитать, но я знаю, что он получил серебро на международной олимпиаде по информатике среди школьников в 2008 году.
UFO just landed and posted this here
Я правильно понимаю, что «динамическое программирование» — это «лишь» один из видов применения понятия «рекурсия»?
Ну, то есть что всё программы, полученные посредством динамического программирования рекурсивны, но не все рекурсивные программы можно отнести к динамическому программированию?
Ну, то есть что всё программы, полученные посредством динамического программирования рекурсивны, но не все рекурсивные программы можно отнести к динамическому программированию?
Любая динамика определяется рекурсивно — без этого нельзя свести задачу к меньшим подзадачам. Если Вы имели в виду это, то да, но реализация рекурсивной функцией обязательна только если порядок обхода был ленивым.
И эта задача обязательно должна быть подобна тем меньшим задачам, на которые её разбивают, и соответственно, они тоже должны мочь разбиваться на самоподобные задачи меньшей мощности (ну, вплоть до граничных случаев). То бишь, по сути — задача должна быть фрактальна! Да?
В принципе да, хотя слово «фрактал», на мой взгляд, тут не самое уместное. А ещё бывают всякие интересные случаи, например, когда одна задача решается с помощью значений состояний другой задачи, которая в свою очередь, основывается на значениях первой — такая запутанная динамика. Сейчас уже пример не вспомню, но такое действительно иногда встречается.
Небольшая поправочка к первому примеру. Ответ будет не сумма *всех* состояний а сумма состояний при (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);
}
Не путайте условие и состояние динамики. Состояние не обязательно должно быть прямо ответом на задачу — в моем состоянии это сообщения ровно за
Как написали ниже, я решил задачу не оптимально, можно и одномерно решить.
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;
}
А для задачи с СМСками правда требуется многомерная динамика? Просто пройтись циклом по количеству нажатий недостаточно?
Достаточно странное и неверное определение ДП.
Ленивая динамика, так же, ненужный и не ясный термин
Ленивая динамика, так же, ненужный и не ясный термин
UFO just landed and posted this here
Написал в продолжение этой статьи со ссылкой на нее
Как найти возможные суммы из N элементов в массиве
https://habr.com/ru/post/599439/
Огромное спасибо автору
Sign up to leave a comment.
Всё, что вы хотели знать о динамическом программировании, но боялись спросить