Достигните N от 1, увеличив значение на 1 или удвоив значение не более чем D раз.

Учитывая целое число N и целое число D , задача состоит в том, чтобы достичь N из 1 за минимальное количество ходов, либо добавив 1, либо удвоив значение, но удвоение может быть выполнено не более D раз.

Примеры:

Input: N = 20, D = 4
Output: 5
Explanation: The flow can be seen as 1 -> 2 -> 4 -> 5 -> 10 -> 20

Input: N = 10, D = 0
Output: 9

Подход: Задачу можно решить с помощью рекурсии:

• Объявите переменную для хранения минимальных ходов в качестве ответа
• Сначала проверьте, достигнута ли цель , если да, найдите минимум текущих ходов и ответьте в ответе .
• Затем проверьте, исчерпаны ли ходы удвоения D , но цель еще не достигнута,
  • Затем добавьте оставшиеся ходы как увеличивающиеся ходы, добавив ( N-current_value ) в current_moves.
  • Найдите минимум current_moves и ans и сохраните в ans
• Если current_value пересекло N , верните
• Если ни один из вышеперечисленных случаев не соответствует, рекурсивно вызовите функцию, чтобы сделать оба нижеприведенных шага один за другим:
  • удвоить текущее_значение
  • добавить 1 к текущему_значению.
• Вернуть окончательный ответ .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)