На протяжении 2 месяцев неспешно решаю задачки на leetcode (нарешал 87 easy, 92 medium, 32 hard, в топ 20% по соревнованиям), параллельно почитываю всякое. Всякие backtracking, BFS, DFS — здорово зашли. Динамическое программирование не идёт, и всё тут. Т.е. я более-менее понимаю как и засчёт чего оно работает, но все задачки, где его можно уместно применить, либо сразу решаю влёт не задумываясь, либо сижу несколько часов — и даже на чужое решение (много чужих решений) смотрю и не понимаю. Часто вижу как решения построены на какой-то очень хитрой логике, которую иначе как хитрожопая сообразительность и не назовёшь. Посоветуйте как поднять уровень — может книжка хорошая есть, может какой-то набор задачек с медленно возрастающим уровнем сложности?

Сейчас вот решал:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Краткий пересказ.

Даны цены на акции по дням, например prices=[7,1,5,3,6,4]. Можно покупать и продавать 1 акцию. На руках можно держать только 1 акцию. Т.е. если акции нет, её можно купить. Если акция есть, её можно продать. Но если акция есть, вторую купить нельзя. Требуется вычислить наибольший профит, который можно получить если покупать и продавать в правильные дни. В случае предложенного примера ответ будет 7 (покупаем за 1, продаём за 5, покупаем за 3, продаём за 6, выходит: 5-1+6-3=7)

Я сделал полный перебор с мемоизацией — не проходит по времени. Добавил пару if'ов, чтобы некоторые случаи не рассматривать, прошёл по времени — "быстрее, чем 5% всех решений". Молодец, ага.

Стал смотреть чужие решения, товарищ вот тут сделал решение со сложностью O(N). Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным Что сделать, чтобы мозг на таких вещах не клинило?

Здравствуйте, rosencrantz, Вы писали:

R>вот тут[/url] сделал решение со сложностью O(N). Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным

А тебе разве нужен "глобальный"?

Здравствуйте, rosencrantz, Вы писали:

R>Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным

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

R>Что сделать, чтобы мозг на таких вещах не клинило?

Окей, а ты покупал когда-нибудь на бирже всамделишние акции?

R> Т.е. если акции нет, её можно купить. Если акция есть, её можно продать.

Можно отбросить эти ненужные ограничения. На бирже можно купить акцию, даже если свободных денег нет (взять деньги в долг под обеспечение); и можо продать акцию, даже если её на руках нет (открыть короткую позицию). Но можно и оставить эти ограничения для простоты.
Представь, что у тебя есть подсказка из хрустального шара — будущий график какой-то акции. Давай даже для интереса предположим, что график непрерывный (а не дискретный, как в реальности) — то есть ты не можешь перебирать по всему континууму точкек.

Разве не очевидно, что тебе надо ловить интервалы возрастания, покупать вначале каждого такого интервала, а продавать в конце? И что если ты купишь не «на низах», а в окрестности (хоть слева, хоть справа локального минимума) то получишь субоптимальный результат? (И то же для продажи не «на верхах», а чуть мимо.)

Ещё для интуиции: представь, что график цены акции — синусоида. Глобально она никуда не растёт. Если покупаешь и продаёшь в случайные моменты времени, то в среднем выйдешь в ноль. Но если ты заранее знаешь, что это синусоида и знаешь её период и фазу, то понятно же, что ты можешь бесконечно богатеть на каждом промежутке возрастания, накапливая их все, и отсиживаясь в кэше на каждом промежутке убывания, а-ля храповик.

Здравствуйте, bobsmith, Вы писали:

B>Здравствуйте, rosencrantz, Вы писали:

R>>вот тут[/url] сделал решение со сложностью O(N). Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным

B>А тебе разве нужен "глобальный"?

Да. Я имею в виду, что возможно несколько стратегий когда будет какой-то профит, но он не будет максимальным возможным. Вот в решении O(N) я понимаю, что профит есть, но не понимаю почему он максимальный возможный.

Здравствуйте, Qbit86, Вы писали:

Q>Здравствуйте, rosencrantz, Вы писали:

R>>Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным

Q>Я пытаюсь представить твою возможную модель задачи, но всё-таки не могу понять, почему «совершенно не понятно почему он будет глобальным».

У меня в голове крутится картинка [1, 2, 100, 2, 1000] и вот хоть убей я не понимаю почему купив за 1, мы должны продавать за 100, а не за 1000.

R>>Что сделать, чтобы мозг на таких вещах не клинило?

Q>Окей, а ты покупал когда-нибудь на бирже всамделишние акции?

Ага, и я даже в плюсе. Но я редко продаю.

R>> Т.е. если акции нет, её можно купить. Если акция есть, её можно продать.

Q>Можно отбросить эти ненужные ограничения. На бирже можно купить акцию, даже если свободных денег нет (взять деньги в долг под обеспечение); и можо продать акцию, даже если её на руках нет (открыть короткую позицию). Но можно и оставить эти ограничения для простоты.
Q>Представь, что у тебя есть подсказка из хрустального шара — будущий график какой-то акции. Давай даже для интереса предположим, что график непрерывный (а не дискретный, как в реальности) — то есть ты не можешь перебирать по всему континууму точкек.

Q>Разве не очевидно, что тебе надо ловить интервалы возрастания, покупать вначале каждого такого интервала, а продавать в конце?

Очевидно, что это будет в плюс. Не очевидно почему это будет наибольший профит.

Q>И что если ты купишь не «на низах», а в окрестности (хоть слева, хоть справа локального минимума) то получишь субоптимальный результат? (И то же для продажи не «на верхах», а чуть мимо.)

Это очевидно. Мне не очевидно как результат вообще может быть НЕ субоптимальным Вот я сейчас продам на локальном максимуме, а завтра оно ещё в 10 раз вырастет.

Q>Ещё для интуиции: представь, что график цены акции — синусоида. Глобально она никуда не растёт. Если покупаешь и продаёшь в случайные моменты времени, то в среднем выйдешь в ноль. Но если ты заранее знаешь, что это синусоида и знаешь её период и фазу, то понятно же, что ты можешь бесконечно богатеть на каждом промежутке возрастания, накапливая их все, и отсиживаясь в кэше на каждом промежутке убывания, а-ля храповик.

Про синусоиду полностью понятно. Не понятно почему в контексте этой задачи синусоиду уместно рассматривать как качественную модель.

Здравствуйте, rosencrantz, Вы писали:

R>У меня в голове крутится картинка [1, 2, 100, 2, 1000] и вот хоть убей я не понимаю почему купив за 1, мы должны продавать за 100, а не за 1000.

Можно и за тысячу, тоже неплохой вариант на практике — когда не знаешь заранее колебания внутри отрезка, но веришь в рост на дистанции. Но если рассмотреть проекции промежутков возрастания на вертикальную ось, то у тебя промежутки 1↗100 и 2↗1000 пересекутся промежутком 2↗100. И если сделать промежуточную продажу за 100 и откупиться обратно за 2, то промежуток роста 2↗100 ты используешь дважды, а промежуток падения 100↘2 пропускаешь вовсе.

R>Вот я сейчас продам на локальном максимуме, а завтра оно ещё в 10 раз вырастет.

Если ты сейчас на локальном максимуме, это по определению означает, что дальше неизбежно начнётся интервал убывания, даже если очень короткий. Если «завтра оно ещё в 10 раз вырастет», значит, этот интервал убывания дойдёт до (как минимум одного) локального минимума, и начнётся возрастание, чтобы «ещё в 10 раз» вырасти. Идея алгоритма в том, чтобы этот интервал убывания пропустить: не сидеть в акциях, а переждать в кэше. И потом заново откупиться, чтоб не пропустить рост «ещё в 10 раз».

Если ты не можешь себе представить такой промежуточный интервал убывания, значит не верна твоя предпосылка, что «я сейчас... на локальном максимуме». То есть «сейчас» не локальный максимум, а просто промежуточная точка без смены направления монотонности: чуть раньше было меньше, чуть позже будет больше; продавать не надо.

Здравствуйте, rosencrantz, Вы писали:

R> Что сделать, чтобы мозг на таких вещах не клинило?

ДП, если не считать общеизвестные алгоритмы вроде Вагнера-Фишера для подсчёта расстояния Левенштейна, в реальном мире используют полтора землекопа. Поэтому если хочется научиться имеено писать олимпиадные алгоритмы, то проще будет смотреть готовые решения и разбирать. По крайней мере, нам так это преподавали в алгоритмической школе. Что касается строгого доказательства, то из разговоров с матёрыми олимпиадниками (это которые дипломы на России берут и на межнар ездят) я знаю, что они порой сдают недоказанные решения, просто уже интуитивно чувствуют, что оно верное или уже решали подобную задачу, но с другим бэкграундом. Лично я, например, если после прочтения хочу написать жадник, пытаюсь придумать случай, когда он не даёт оптимальное решение, и если нахожу, то сразу понимаю, что это ДП. Если же цель — собеседования, то проще запомнить все задачи, которые могут задавать, их не так много, потому что обычно в компании есть пул, из которого берут задачи, и который быстро утекает на сторону.

P.S. Ещё со школы помню задачу, на которой мой подход впервые поломался — разбить прямоугольник на наименьшее количество квадратов. Там интересно то, что ни жадниый алгоритм, ни ДП не дают оптимальное решение в общем случае.

Здравствуйте, rosencrantz, Вы писали:

R>Стал смотреть чужие решения, товарищ вот тут сделал решение со сложностью O(N). Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным Что сделать, чтобы мозг на таких вещах не клинило?

Задача решается в одну строчку (питон)
Идея в том, что каждое положительное изменение цены записывать себе в плюс.

return sum(max(p2-p1, 0) for p1, p2 in zip(prices, prices[1:]))

Честно говоря, у меня тоже не укладывается в голове, почему это работает. С одной стороны логично, с другой — чувствуется какой-то подвох.

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

Здравствуйте, Буравчик, Вы писали:

Б>Честно говоря, у меня тоже не укладывается в голове, почему это работает. С одной стороны логично, с другой — чувствуется какой-то подвох.

Так нет подвоха — если мы заранее знаем цены, то всегда торгуем оптимальным образом.

Здравствуйте, rosencrantz, Вы писали:

R>Посоветуйте как поднять уровень — может книжка хорошая есть, может какой-то набор задачек с медленно возрастающим уровнем сложности?
Если хочется спортивного — есть классический учебник: АлгоритмыЙ построение и анализ, так же известный в спортивных кругах как "Осёл" (по оформлению первой редакции). Там есть и разбор тем, и задачи по возрастанию сложности.

R>Я сделал полный перебор с мемоизацией — не проходит по времени. Добавил пару if'ов, чтобы некоторые случаи не рассматривать, прошёл по времени — "быстрее, чем 5% всех решений". Молодец, ага.

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

Эту задачу можно решать динамикой. Мы вычисляем максимальный доход (значение функции) на конец дня (номер дня — первое измерение) и отдельно для наличия и отсутствия акции (это второе измерение из всего двух элементов — "есть акция" и "нет акции"). Предлагаю вам составить рекуррентные соотношения для вычисления значения функции на конец следующего дня.

Вообще динамика считается достаточно сложной и в спортивном программировании. Основные факторы:

• Могут быть ранзые размерности. Обычно N=2 или N=3. Реже N=1. В исключительных случаях N>=4.
  
• Измерения для функции бывают очень разные и экзотические. "Часть ввода" (как у вас), "часть алфавита", "искусственное состояние" (это тоже ваша задача), "возможный ответ". Реже, но тоже бывает что-нибудь вроде "сумма чего-нибудь".
  
• В зависимости от задачи и формы функции может считаться весь N-мерный куб (ваш случай). А может обсчитываться только его половина (другая половина вообще смысла не имеет).
  
• Рекурентная формула может зависеть только от "ближних" значений (ваш случай и 75% задач на всяких leetcode будут такие), а может от любого из "предыдущих".
  
• Рекурентная формула может иметь фиксированное число ветвлений (и это тоже у вас), а может и "динамическое" (например, итерация от 0 до значения N-го элемента из ввода). Обычно во втором случае нужны и все ранее вычисленние значения (не только локальные).

R>Стал смотреть чужие решения, товарищ вот тут сделал решение со сложностью O(N).

Так это не динамика (динамическое программирование). Это вполне обычная жадница (жадный алгоритм).

R>Но совершенно не понятно почему он будет глобальным

Раз жадница, то и доказывается по схеме жадницы. Рассмотрим некоторое оптимальное решение. Пусть у нас есть два последовательных дня с ценами a и b. Пусть a < b, тогда в этом (оптимальном) решении у нас на конец дня a есть акция на руках. Почему? Докажем от противного. Пусть акции нет. Тогда рассмотрим, что у нас было на начало дня a и на конец дня b. Возможны четыре варианта.

• (нет, нет) — Строим новое решение, почти во всем повторяющее оптимальное. Но при этом покупаем акцию в первый (ну т.е. в "день a"), продаем во второй день. Все остальные манипуляции — те же. Но мы получили дополнительный доход в размере (b-a). Т.е. исходное решение было не оптимальным. Противоречие.
  
• (да, нет) — Принцип тот же. Мы продали акцию в день a. В новом решении мы продаем ее в день b и получаем лучшее решение.
  
• (нет, да) — вместо покупки в день b покупаем в день a.
  
• (да, да) — вспоминаем, что на конец дня a у нас не было акции (это наше предположение про решение). Т.е. мы продали акцию за a и купили за b. Тогда мы просто не продаем акцию за a (ну и не покупаем за b). Profit!

Для случая a > b аналогично доказывается, что на конец дня a у нас нет акции (в оптимальном решении).

И вот по этой схеме доказывается 90% жадных алгоритмов. Оставшиеся 10% доказываются чуть сложнее. Там обычно строится цепочка эквивалентных преобразований алгоритмов. Т.е. "мы делали сначала A потом Б, но можно было бы сделать сначала Б а потом А с тем же результатом". И в цепочке показывается, что можно применить эти преобразования несколько раз и свести любой оптимальный алгоритм к тому, что строится жадным.

R>Что сделать, чтобы мозг на таких вещах не клинило?

Нужно найти олимпиадников и тренироваться с ними. Самое важное здесь — это фаза триажа. Когда вам выдается сразу 10 (+-epsilon) задач и вам нужно с ходу отобрать, что идет в написание. И потом в течение нескольких часов оценивать перспективы решения (вашей командой) каждой из оставшихся нерешенных задач. Отработка конкретного алгоритма или подхода тоже может использоваться. Но из моей практики это только для отработки проблемных моментов. Остальное — триаж и куча практики.

Здравствуйте, maxkar, Вы писали:

M>А динамика (динамическое программирование) где? Отличительным принципом динамики является сведение задачи к вычислению функции, заданной рекурентным соотношением на N-мерном кубе.

А где про связь динамики и n-мерного куба можно подробнее почитать?

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

А что не так с мемоизацией в этом подходе, если обход куба осущ. рекуррентно?

M>Вообще динамика считается достаточно сложной и в спортивном программировании.

Блин, а какая техника в спорт. прог. есть сложнее динамики?

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

Здравствуйте, rosencrantz, Вы писали:

R>Посоветуйте как поднять уровень — может книжка хорошая есть, может какой-то набор задачек с медленно возрастающим уровнем сложности?
Сразу скажу, что готового совета нет — я просто случайно прочитав ваше сообщение, по скорости наткнулся на Litres вот на такую книгу: Динамическое программирование. Да, она заявлена как "для школьников и студентов", но, быть может, поработав с ней вы что-то сможете утрясти в собственном понимании.

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

P.S. Да, на Litres эта книга не доступна для скачивания, а только в варианте "через приложение Litres или на сайте", что для меня, например, сразу ставит на ней крест (с сайта там еще более-менее, но их приложение, это что-то кошмарно-неудобное). Может, для вас это и не критично, но имейте в виду.

Здравствуйте, rosencrantz.
Имхо очень хреновая задача чтобы потренить DP, в разы легче думать о положительном изменении цены чем о том, где тут искать рекурентные отношения и какой стейт создавать.
По поводу самого DP на том же литкоде есть прикольный курс:
leetcode.com dynamic-programming

Плюс еще мне вот этот видос понравился.
Dynamic Programming &mdash; Learn to Solve Algorithmic Problems &amp; Coding Challenges


По поводу задач, лучше возьми эти:
house-robber
delete-and-earn
n-th-tribonacci-number

На них как минимум проще придумать top-down решение и преобразовать его в bottom-up

Здравствуйте, Sharov, Вы писали:

S>А где про связь динамики и n-мерного куба можно подробнее почитать?

А она из определения динамики как вычисления рекуррентной формулы не следует? В литературе про это вроде бы ничего нет, но я особо и не интересовался.

M>>И практически всегда она реализуется обходом точек куба и вычислением функции в правильном порядке. Да, можно и мемоизацией обойтись. Но скорее она является индикатором того, что вы что-то делаете неправильно.
S>А что не так с мемоизацией в этом подходе, если обход куба осущ. рекуррентно?

"Неправильно" — это интуитивно . Но вообще да, есть и практическая причина. Не все задачи на динамику могут быть решены запоминанием. Периодически встречаются такие, где в память влезает только две-три итерации (текущая и одна-две предыдущих). Рекуррентная формула там зависит только от одного (и гораздо реже — двух и более) предыдущих итераций. Может быть, некоторым задачам может не хватить стека, не знаю. И вот у нас получается, что половина (а то и больше) задач на динамику решается мемоизацией. А другая — не решается. Кроме того, базовая эвристика (по размерности входных данных) может привести к выводу, что "не влезает в память — не динамика". Но ту половину, которая не решается мемоизацией, тоже хотелось бы уметь решать. Т.е. нужно тренироваться различать как минимум две реализации одного алгоритма. Но это еще мелочи. В "сложной" половине задач нужно увидеть схему вычисления. Для мемоизации схема не нужна, там можно в любом порядке вычислять. А это значит, что мозг (нейронная сетка) не очень тренирован распознавать зависимости и строить "слои" вычислений (грубо говоря, в многомерном кубе есть некоторое общее направление всех векторов зависимостей, вдоль него обычно и строятся вычисления). В "сложных" задачах обычно схему заметить сложнее. В них как больше количество возможных "осей" (обычно пара-тройка осей и служит для создания требований по памяти). Т.е. разработчику приходится сразу решать сложную задачу и без соответствующей тренировки мозга.

А вот "послойный" обход универсален. Можно тренировать "один" распознаватель задач вместо двух (один для простых, другой для сложных). Этот распознаватель будет использоваться большее количество времени, чем каждый из раздельных. Кроме того, у решателя есть много практики простроения схем вычислений на простых задачах. Есть "большое количество тренировочного материала". Поэтому вероятность того, что нужный паттерн будет распознан в сложном случае тоже выше.

S>Блин, а какая техника в спорт. прог. есть сложнее динамики?

Максимальные паросочетания в двудольном графе. Максимальный поток. Хотя все индивидуально. В реальных командах есть распределение обязанностей. Поэтому для кого-то может стать большой проблемой какой-нибудь поиск подстроки в строке (я такое сейчас напишу, но потрачу минут 10-15 на то, чтобы вспомнить детали). К счастью, большинство алгоритмов можно запомнить. Сложны обобщенные схемы вроде динамического программирования и жадных алгоритмов. Иногда бывает какая-нибудь геометрия или математика. Бывает региональная мода (например, задачи на точность вычисления с плавающей точкой). Ну и вишенкой идут многоходовки, где нужно применять два и более алгоритмов.

Здравствуйте, maxkar, Вы писали:

S>>А где про связь динамики и n-мерного куба можно подробнее почитать?
M>А она из определения динамики как вычисления рекуррентной формулы не следует? В литературе про это вроде бы ничего нет, но я особо и не интересовался.

А вот без понятия, поэтому и спросил. Т.е. какой-то геом. интуиции под дин. прог. я не замечал и не видел\слышал.
А почему n-мерный куб, мы разве по кубу обходим? Почему не другая фигура? Не понимаю связи рекуррентной формулы и геометрии...

Здравствуйте, -n1l-, Вы писали:

N>Плюс еще мне вот этот видос понравился.
N>Dynamic Programming &mdash; Learn to Solve Algorithmic Problems &amp; Coding Challenges


https://www.youtube.com/watch?v=AawQnuYSY4Y&amp;list=PLUfHxBkkFMScK6mOOWp5s6LgbzmtfwmYQ -- еще этот плейлист
рекомендовали

Здравствуйте, Sharov, Вы писали:

S>А вот без понятия, поэтому и спросил. Т.е. какой-то геом. интуиции под дин. прог. я не замечал и не видел\слышал.
Это скорее алгебраическая интуиция. Множество точек 0 <= x1 <= B1, 0 <= x2 <= B2, ... 0 <= xn <= Bn. С геометрией у меня плохо.

S>А почему n-мерный куб, мы разве по кубу обходим? Почему не другая фигура? Не понимаю связи рекуррентной формулы и геометрии...
Не обязательно строго по кубу. Бывают призмочки (обычно с треугольным основанием). Бывают пирамидки. И все — вписанные в куб.

Связь — функция (т.е. значения рекурретного выражения) вычисляется путем вложенных for'ов. Не меморизация, а именно итерация определенный порядок. Ну например, в исходной задаче у нас будет что-то вроде

profit[0, false] = 0 // доход на начало дня
profit[0, true] = Integer.MIN_VALUE // недостижимо

for day in 1 to N
  /* for hasShare in [false, true] */
  profit[day, false] = max(profit[day - 1, false], profit[day - 1, true] + prices[day-1])
  profit[day, true] = max(profit[day - 1, true], profit[day - 1, false] - prices[day-1])

Обход идет по дню и потом (внутри дня) по наличию акции.

Для других задач итерации от края до края не обязательна, может быть что-то вроде

data[0, 0] = ...

for x in 1 to N
  data[x, 0] = ... // init
  for y in 1 to fn(x)
    data[x, y] = ...

Или инициализация может быть по ребрам и потом внутри по формуле:

for x in 0 to N
  data[x, 0] = ...
for y in 0 to N
  data[0, y] = ...

for x in 1 to N // порядок вычислений
  for y in 1 to N // тоже порядок
    acc = something
    for x1 in 0 to x-1 // часть рекуррентной формулы
      for y1 in 0 to x-1 // тоже часть рекуррентной формулы
        acc = min(acc, data[x1, y1])

Ну и прочие вариации. Но практически вся динамика сводится к вычислению (основной части) целевой функции через комбинацию вложенных for. Границы там могут немного варьироваться, но общая структура задает фигуру внутри "куба" (квадрата, и прочиха альтернативных размерностей). Я не могу вспомнить из практики задачу, где вычисление не сводилось бы к этим вложенным if'ам. Можно придумать что-нибудь, где обход "хаотический" и нужно делать именно мемоизацию. Будет большая подстава

Здравствуйте, maxkar, Вы писали:

M>Связь — функция (т.е. значения рекурретного выражения) вычисляется путем вложенных for'ов. Не меморизация, а именно итерация определенный порядок. Ну например, в исходной задаче у нас будет что-то вроде

M>

M>profit[0, false] = 0 // доход на начало дня
M>profit[0, true] = Integer.MIN_VALUE // недостижимо

M>for day in 1 to N
M>  /* for hasShare in [false, true] */
M>  profit[day, false] = max(profit[day - 1, false], profit[day - 1, true] + prices[day-1])
M>  profit[day, true] = max(profit[day - 1, true], profit[day - 1, false] - prices[day-1])
M>

Ну а разве изпользование предыдущего выч. значения типа profit[day — 1, false] не мемоизация? Мы же его не перевычисляем?

Здравствуйте, Sharov, Вы писали:

S>Ну а разве изпользование предыдущего выч. значения типа profit[day — 1, false] не мемоизация? Мы же его не перевычисляем?

Это сложный терминологический спор, близкий к религиозному . С моей точки зрения — нет, не мемоизация а вычисление таблицы значения (lookup table) функции. Мемоизация более ленивая. Т.е. когда вызвали функцию, мы проверили кэш, вызвали функцию, сохранили результат. В кэше оказываются только те значения, которые были реально нужны для получения результата. При вычислении таблицы значений мы просто вычисляем все значения на области определения функции, вне зависимости от того, используются ли они для получения финального результата.