Permite que dp [N] [2] sea nuestra unidad memorable.
Estados ->
- dp [k] [0] = número de k dígitos que satisfacen la condición del problema pero terminan en cero.
- dp [k] [1] = número de números de k dígitos que satisfacen la condición del problema pero que terminan en uno.
Claramente podemos ver eso:
dp [0] [1] = dp [0] [0] = 1
Digamos que tenemos que encontrar la respuesta para los dígitos ‘k’ siempre que sepamos la respuesta óptima para los dígitos ‘k – 1’. Asi que,
- ¿Puede una computadora generar un número verdaderamente aleatorio?
- ¿Existe algún libro de estructuras de datos y algoritmos en C ++ (tiene código fuente completo en C ++) disponible de forma gratuita en Internet?
- ¿Cómo se realiza la coincidencia de cadenas en SQL?
- ¿Existe un mejor patrón para aprender algoritmos de programación?
- ¿Por qué no ha habido un codificador indio en la región 2400+ después de Rudradev Basak, especialmente cuando la cultura de codificación en el país está en aumento?
- dp [k] [0] = dp [k – 1] [1]
- dp [k] [1] = dp [k – 1] [0] + dp [k – 1] [1]
Respuesta = dp [k] [0] + dp [k] [1]
EDITAR:
Al observar un poco, podemos decir que todo lo que tenemos que hacer es encontrar el número k’th de Fibonacci. El valor de ‘k’ puede ser (<= 10000), la respuesta no se ajustará en un rango largo largo (64 bits), por lo tanto, tenemos que usar aritmética larga y larga, es decir, calcular la respuesta dígito por dígito.
Supongamos que nuestra respuesta cabe en 5000 dígitos.
Estoy usando tres matrices de tamaño 5000
- pre [5000] – almacena el ans para k – 2 dígitos (dígito por dígito).
- cur [5000]: almacena el ans para k – 1 dígitos.
- cal [5000] – la respuesta para k dígitos se almacena en cal, ya que (cal = pre + cur) todo lo que hacemos es agregar los dígitos correspondientes de pre y cur.
Pseudocódigo –
Entrada (k)
Si (k <2):
Imprimir directamente
De lo contrario:
pre [5000] = 2
cur [5000] = 3
PARA i de 3 a k:
cal = cur + pre (suma dígito a dígito)
pre = cur
cur = cal
Imprimir (cal)
