Múltiples soluciones al problema de subir escaleras

Supongamos que estás subiendo escaleras. Se necesitan n pasos para llegar a la cima del edificio.

Puedes subir 1 o 2 escalones a la vez. ¿De cuántas maneras diferentes puedes subir a la cima de un edificio?

Nota: n es un número entero positivo.

Entrada: 2

Salida: 2

Explicación: Hay dos formas de subir a la cima del edificio.

Entrada: 3

Salida: 3

Explicación: Hay tres formas de subir a la cima del edificio.

En el método de fuerza bruta combinaremos todos los pasos posibles, es decir, 1 y 2. En cada paso, continuaremos llamando a riseStairs. La función riseStairs simula los pasos 1 y 2 y devuelve la suma de los valores de retorno de las dos funciones.

subirEscaleras(i,n) = subirEscaleras(i + 1, n) + subirEscaleras(i + 2, n)

donde i define el orden actual y n define el nivel objetivo.

El árbol de recursividad cuando n=5 se verá así:

En el método anterior, tenemos redundancia en el cálculo del resultado de cada paso. Otra forma de pensar es que podemos almacenar los resultados de cada paso en la matriz de memoria y, cada vez que se vuelve a llamar a la función, devolvemos los resultados directamente desde la matriz de memoria.

Con la ayuda de la matriz de memoria, obtenemos un árbol de recursividad reparado cuyo tamaño se reduce a n.

No es difícil encontrar que este problema se puede descomponer en algunos subproblemas que contienen subestructuras óptimas, es decir, su solución óptima se puede construir efectivamente a partir de las soluciones óptimas de sus subproblemas. Podemos utilizar la programación dinámica para resolver este problema.

El nivel ii se puede obtener mediante los dos métodos siguientes:

Subir 1 nivel tras nivel (i-1).

Después del paso (i-2), sube 2 pasos.

Entonces, el número total de formas de alcanzar el i-ésimo nivel es la suma del número de formas de llegar al (i?1)ésimo nivel y al (i?2)ésimo nivel.

Dejemos que se dé dp.

Intentemos demostrarlo.

Este método lo podemos demostrar mediante inducción matemática. Es fácil ver que esta matriz da el resultado correcto para el ítem 3 (el caso base). Dado que

esto demuestra que la situación básica es cierta.

Supongamos que este método es adecuado para encontrar el enésimo número de Fibonacci, es decir, F n =Q n-1, entonces:

Ahora, necesitamos demostrar que los dos anteriores condiciones Si es verdadero, este método puede encontrar efectivamente el (n+1)ésimo número de Fibonacci, es decir, F n+1 =Q n.

Demostración:

Por lo tanto, F n+1 =Q n . Obtenga la certificación.

El único cambio que necesitamos hacer para nuestro problema es cambiar los términos iniciales de la secuencia de Fibonacci a 2 y 1 en lugar de 1 y 0. Alternativamente, otro enfoque es usar la misma matriz inicial Q y usar resultado = Q n para obtener el resultado final. La razón por la que esto sucede es que tenemos que usar los términos 2 y 3 de la secuencia de Fibonacci original como términos iniciales.

Podemos usar esta fórmula para encontrar el enésimo número de Fibonacci:

Para el problema dado, la secuencia de Fibonacci se definirá como F 0 = 1, F 1 = 1, F 2 = 2, F norte+2 = F norte+1 + F norte . La forma estándar de intentar resolver esta fórmula recursiva es establecer F n de la forma F n = a n .

Entonces, naturalmente tenemos F n+1 = a n+1 y F n+2 = a n+2 , por lo que la ecuación se puede escribir como a n+2 = a n+1 + a n . Si reducimos toda la ecuación, obtenemos a 2 = a + 1 o escrita como ecuación cuadrática a 2 - a- 1= 0.

Resolviendo la fórmula cuadrática, obtenemos:

La solución general tiene la siguiente forma:

Cuando n = 0, hay A + B = 1

Cuando n = 1, tenemos

Resolviendo la ecuación anterior, obtenemos:

Sustituyendo estos valores de AA y BB en lo anterior. En general, al resolver ecuaciones, podemos obtener: