0

Здраствуйте, я только начал свой путь в олимпиадном программировании. Нужно из 0 получить N добавляя два или три. Какое минимальное количество операций потребуется?

2
  • Пожалуйста, уточните вашу конкретную проблему или приведите более подробную информацию о том, что именно вам нужно. В текущем виде сложно понять, что именно вы спрашиваете. 1 ноя 2021 в 16:07
  • смотрите остаток от деления на 3
    – splash58
    1 ноя 2021 в 16:13

1 ответ 1

2

Если непременно нужно решать с помощью ДП (см. комментарий от 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] будет содержать количество шагов.

1

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.