Минимальное количество операций из 0 в N
Здраствуйте, я только начал свой путь в олимпиадном программировании.
Нужно из 0 получить N добавляя два или три. Какое минимальное количество операций потребуется?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Если непременно нужно решать с помощью ДП (см. комментарий от splash58), то нетрудно записать рекурсивную функцию
F(0,N) = min(F(2,N), F(3,N))
На её основе можно сделать мемоизацию - ДП с запоминанием промежуточных результатов.
Но здесь лучше создать массив длиной N+1 и заполнять его снизу, для каждого элемента проверяя -
DP[i] = 1 + min(DP[i-2], DP[i-3])
DP[N] будет содержать количество шагов.