650. Teclado de 2 teclas

Dificultad: Mediana

Temas: Matemáticas, programación dinámica

Solo hay un carácter 'A' en la pantalla de un bloc de notas. Puede realizar una de dos operaciones en este bloc de notas para cada paso:

• Copiar todo: Puede copiar todos los caracteres presentes en la pantalla (no se permite una copia parcial).
• Pegar: puede pegar los caracteres que se copiaron la última vez.

Dado un número entero n, devuelve el número mínimo de operaciones para obtener el carácter 'A' exactamente n veces en la pantalla.

Ejemplo 1:

• Entrada: n = 3
• Salida: 3
• Explicación: Inicialmente, tenemos un carácter 'A'.
  • En el paso 1, utilizamos la operación Copiar todo.
  • En el paso 2, utilizamos la operación Pegar para obtener 'AA'.
  • En el paso 3, utilizamos la operación Pegar para obtener 'AAA'.

Ejemplo 2:

• Entrada: n = 1
• Salida: 0

Ejemplo 3:

• Entrada: n = 10
• Salida: 7

Ejemplo 2:

• Entrada: n = 24
• Salida: 9

Restricciones:

• 1

Pista:

1. ¿Cuántos caracteres puede haber en el portapapeles en el último paso si n = 3? norte = 7? norte = 10? norte = 24?

Solución:

Necesitamos encontrar el número mínimo de operaciones para obtener exactamente n caracteres 'A' en la pantalla. Usaremos un enfoque de programación dinámica para lograr esto.

1. Comprensión del problema:

   • Empezamos con una 'A' en la pantalla.
   • Podemos "Copiar todo" (que copia el contenido de la pantalla actual) o "Pegar" (que pega el último contenido copiado).
   • Necesitamos determinar las operaciones mínimas necesarias para tener exactamente n caracteres 'A' en la pantalla.

2. Enfoque de programación dinámica:

   • Utilice una matriz de programación dinámica (DP) dp donde dp[i] representa el número mínimo de operaciones necesarias para obtener exactamente i caracteres en la pantalla.
   • Inicializa dp[1] = 0 ya que se necesitan 0 operaciones para tener una 'A' en la pantalla.
   • Para cada número de caracteres i del 2 al n, calcule las operaciones mínimas verificando cada divisor de i. Si i es divisible por d, entonces:
     • El número de operaciones necesarias para llegar a i es la suma de las operaciones para llegar a d más las operaciones necesarias para multiplicar d para obtener i.

3. Pasos para resolver:

   • Inicializa una matriz DP con INF (o un número grande) para todos los valores excepto dp[1].
   • Para cada i de 2 a n, itere a través de posibles divisores de i y actualice dp[i] en función de las operaciones necesarias para llegar a i copiando y pegando.

Implementemos esta solución en PHP: 650. Teclado de 2 teclas

Explicación:

• Inicialización: dp se inicializa con un número grande (PHP_INT_MAX) para representar un estado inicialmente inalcanzable.
• Verificación de divisores: Para cada número i, verifique todos los divisores d. Actualice dp[i] considerando las operaciones necesarias para llegar a d y luego multiplicando para obtener i.
• Salida: El resultado es el valor de dp[n], que proporciona las operaciones mínimas necesarias para obtener exactamente n caracteres en la pantalla.

Este enfoque garantiza que calculemos las operaciones mínimas de manera eficiente para las restricciones dadas.

Enlaces de contacto

Si esta serie te resultó útil, considera darle al repositorio una estrella en GitHub o compartir la publicación en tus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si quieres más contenido útil como este, no dudes en seguirme:

• LinkedIn
• GitHub