Блог пользователя dudeboy

И снова помогите решить задачу на ДП
Автор dudeboy, 13 лет назад, По-русски

Теперь мучаюсь над этой задачей:  http://acmp.ru/index.asp?main=task&id_task=169
Помогите с разбором, пожалуйста. 

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

При решении задачи на ДП нужно понять 3 вещи:
1) Что будет состоянием?
2) Что будем хранить для каждого состояния?
3) Как будем делать переход?

Здесь все что мы знаем или хотим узнать - это (в скобках указаны равнозначные альтернативы):
1) Расстояние до магазина.
2) Сколько шагов мы уже сделали (нам еще предстоит сделать).
3) Сколькими способами можно достичь этого (сколькими способами можно добраться до магазина).

Осталось решить, что из этого будет состоянием и что мы будем хранить, а так же придумать переход. Вперед :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
dudeboy, прочти сначала Котова "Динамическое программирование". В свое время книжка сильно помогла мне понять суть ДП.
http://g6prog.narod.ru/din_kotov.rar
→ Ответить