Dado qualquer número n e três operações em n:

add 1subtrair 1divida por 2 se o número for par

Quero encontrar o número mínimo de operações acima para reduzir n para 1. Tentei a abordagem de programação dinâmica, também BFS com poda, mas n pode ser muito grande (10 ^ 300) e não sei como criar meu algoritmo Mais rápido. A abordagem gananciosa (divida por 2 se for par e subtraia 1 se for ímpar) também não fornece o resultado ideal. Existe outra solução?