Дистанционная подготовка: Ревью кода
Ревью кода
от Большаков Дмитрий - Четверг 11 Октябрь 2012, 18:20
915. Платная лестница
  Никак не могу пройти хоты бы одного теста. Если не сложно, можете сделать ревью кода. Номер посылки: 245-7603
Re: Ревью кода
от Peter Cherepanov - Четверг 11 Октябрь 2012, 22:30
  Во-первых, ваш комментарий обрабатывается как программа.

Во-вторых, эта задача жадным алгоритмом не решается.
Посмотрите, что такое "динамическое программирование".
Re: Ревью кода
от Большаков Дмитрий - Четверг 11 Октябрь 2012, 23:55
  Спасибо, комментарий убрал, стало веселее.
На странице задачи есть ссылочка "разбор", которая разворачивает такое содержание:

"Пусть f - функция динамического программирования. На i-ю ступеньку мальчик мог попасть только с (i-1)-й или с (i-2)-й ступенек. Значит f[i] = min(f[i-1], f[i-2]) + стоимость i-й ступеньки."

Собственно, это, как мне кажется, и реализовано (Посылка номер 245-7605). Подсказка неверна? Или косяк у меня?
Re: Ревью кода
от Денис Кириенко - Пятница 12 Октябрь 2012, 18:12
  У вас ошибка в реализации, программа падает
IndexError: list index out of range
Re: Ревью кода
от Большаков Дмитрий - Пятница 12 Октябрь 2012, 19:18
  Динис, спасибо за подсказку. Теперь все OK
Re: Ревью кода
от Никита Пушкин - Суббота 3 Май 2014, 17:59
  А почему не жадным?
Re: Ревью кода
от Никита Пушкин - Суббота 3 Май 2014, 18:14
  Так, понял, почему. Значит, разбор неверный. Как тогда решить эту задачу?
Re: Ревью кода
от Григорий Резников - Пятница 16 Май 2014, 15:43
  Разбор-то правильный, и в разборе не жадность, а динамика