ДП очень похоже на мемоизацию. Два главных преимущества:
1. Итерация вместо рекурсии: не надо беспокоиться о стеке.
2. Мемоизация решает задачи «сверху вниз», а ДП — «снизу вверх». ДП экономит память за счет того, что можно выкидывать решения подзадач, которые больше не понадобятся: если подзадача (m,n) зависит только от (m-1,n-1) и (m-1,n), то для вычисления (5,1)...(5,5) нужны только (4,1)...(4,5), все предыдущие значения хранить не надо.
Мемоизация более интуитивная чем ДП, поэтому я обычно решаю задачи так:
1. Рекурсивное решение.
2. Добавляем мемоизацию.
3. Рисуем картинку с порядком вычислений:
4. Выделяем «уровни», чтобы следующий уровень зависел только от предыдущего. В этом примере уровнем может быть строчка или столбец таблицы.
5. ???
6. ДП!!!
Да-да, была одна компания, обещала защитить ваши персональные данные. Главный босс решил выступить личным примером и подразнил «злобных хакеров» на биллбордах по всей стране. Думаю он неоднократно пожалел потом.
Я себе сделал маленькую приблуду на google apps, которая отличает телефон от нормального компьютера и перенаправляет на мобильный или полноценный хабр, соответственно при открытии ссылки из рсс. Если интересует, могу описать подробнее отдельной статьей.
1. Итерация вместо рекурсии: не надо беспокоиться о стеке.
2. Мемоизация решает задачи «сверху вниз», а ДП — «снизу вверх». ДП экономит память за счет того, что можно выкидывать решения подзадач, которые больше не понадобятся: если подзадача (m,n) зависит только от (m-1,n-1) и (m-1,n), то для вычисления (5,1)...(5,5) нужны только (4,1)...(4,5), все предыдущие значения хранить не надо.
Мемоизация более интуитивная чем ДП, поэтому я обычно решаю задачи так:
1. Рекурсивное решение.
2. Добавляем мемоизацию.
3. Рисуем картинку с порядком вычислений:
4. Выделяем «уровни», чтобы следующий уровень зависел только от предыдущего. В этом примере уровнем может быть строчка или столбец таблицы.
5. ???
6. ДП!!!
Я только немножко не уверен, что (n/p)/p будет равно n/(p*p), с учетом целочисленного деления. Надо подумать.