Un niño que sube una escalera con n escalones puede subir 1, 2 o 3 escalones a la vez. ¿De cuántas maneras puede llegar el niño a la cima?

La programación dinámica es una de esas áreas donde se necesita un poco de práctica para acostumbrarse. Para decirlo sin rodeos, no es una aplicación de sentido común simple a menos que ya lo sepas. Es por eso que se enseña en casi cursos de diseño de algoritmos CS y se usa en la mayoría de las entrevistas de algoritmos. Requiere un poco de alfabetización CS, por estudio académico o autoestudio. Hay tres partes principales para resolver este problema, suponiendo que ya sepa que existe algo llamado programación dinámica y que se puede usar para resolver ciertos tipos de problemas de manera eficiente si satisfacen ciertos criterios. Primero es reconocer que el problema se ajusta al requisito de programación dinámica. El segundo es modelar la esencia del problema en términos matemáticos y finalmente descubrir la solución.

Hay dos características principales de un problema de programación dinámica. Es un problema que puede dividirse en subproblemas y las sub-soluciones se superponen. Esto es lo que necesita recordar para usar la programación dinámica y esta es la parte que no es sentido común sino conocimiento adquirido. Aunque una vez aprendido, se convierte en sentido común para ti.

Para abordar problemas como este, primero debe elaborar ejemplos para algunos casos, tanto básicos como 1, 2, 3 y números más grandes como 10, 11, 12, etc. Una vez que resuelva estos ejemplos, debería verse repitiendo cálculos. En este escenario, todas las combinaciones para 10 también ocurrirán para 11 con un extra 1 y para 12 con un extra 2 y para 13 con un extra 3 o tres 1 o uno 1 y uno 2. Esto debería darle suficiente pista de que el El problema puede dividirse en subproblemas y la superposición de sub-soluciones. De aquí en adelante, se convierte en una aplicación del sentido común y las matemáticas. Intenta obtener una relación de recurrencia como la que se da en otra respuesta para un número genérico N y la verifica para ver ejemplos, lo ha probado. También trabajas tus casos base. En este caso, hay tres casos base diferentes. Creo que ya sabes cómo ir desde aquí. La única parte difícil es reconocer que el problema es un candidato para un problema de programación dinámica. Requiere un poco de intuición y cada problema debe abordarse de manera diferente. No hay una forma deductiva de hacerlo y esta es la razón por la cual los problemas de programación dinámica son los favoritos en las entrevistas. También pone a prueba su intuición junto con capacidades lógicas y alfabetización de algoritmos. El comienzo siempre es encontrar ejemplos y primero intentar enfoques más básicos como el simple enfoque de dividir y conquistar y codicioso. Al observar y analizar ejemplos, debería ser obvio que es un candidato de programación dinámica. Después de suficiente práctica, puede hacerlo simplemente mirando el problema y pensando en la solución de fuerza bruta.

Como mucha gente dijo aquí, esto se puede resolver utilizando la recurrencia:

[matemáticas] s_0 = 1 [/ matemáticas]
[matemáticas] s_1 = 1 [/ matemáticas]
[matemáticas] s_2 = 2 [/ matemáticas]
[matemáticas] s_n = s_ {n-1} + s_ {n-2} + s_ {n-3} [/ matemáticas]

Simplemente escribiendo esto como una recursión, tendrá un algoritmo exponencial en n (aproximadamente [matemáticas] O (1.84 ^ n) [/ matemáticas]). Puede usar la programación dinámica o la memorización para hacerlo en operaciones aritméticas [matemáticas] O (n) [/ matemáticas]. Si no le importa la precisión, puede usar la solución de Mark Gritter que produce una fórmula de forma cerrada. Ver su explicación, es muy claro.

Si le importa su precisión, puede resolverla usando álgebra lineal. Definamos el vector [math] S_n = (s_n \ quad s_ {n + 1} \ quad s_ {n + 2}) ^ T [/ math]. Para [math] n> 0 [/ math] intentemos escribir [math] S_i [/ ​​math] en términos de [math] S_ {n-1} [/ math]. (Tenga en cuenta que [math] s_n [/ math] y [math] s_ {n + 1} [/ math] son ​​partes de [math] S_n [/ math] y [math] S_ {n-1} [/ math ].)

[matemáticas] s_n = s_n [/ matemáticas]
[matemáticas] s_ {n + 1} = s_ {n + 1} [/ matemáticas]
[matemáticas] s_ {n + 2} = s_ {n + 1} + s_i + s_ {n-1} [/ matemáticas]

Esto se puede reescribir de una manera más ordenada utilizando la notación matricial. A saber:
[matemáticas] S_n = \ left (\ begin {matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \ end {matrix} \ right) S_ {n-1} = AS_ {n -1} [/ matemáticas]

Al usar la inducción, se puede demostrar fácilmente que [matemática] S_n = A ^ n S_0 [/ matemática] y [matemática] S_0 = (1 \ quad 1 \ quad 2) [/ matemática]. Entonces podemos calcular [matemáticas] A ^ n [/ matemáticas] con [matemáticas] O (log n) [/ matemáticas] operaciones aritméticas usando Exponenciación por cuadratura.

Nota 1: Dado que [math] s_n [/ math] crece exponencialmente con [math] n [/ math], su tamaño (número de bits) crece linealmente. Entonces es técnicamente imposible tener una solución en menos de tiempo lineal si se desea una precisión total. Si bien mi solución realmente hace un número logarítmico de operaciones aritméticas, las operaciones mismas involucran números cada vez más grandes.

Nota 2: No es sorprendente que los valores propios de [matemática] A [/ matemática] sean [matemática] (1.8392) [/ matemática], [matemática] -0.41964 – 0.60629i [/ matemática] y [matemática] -0.41964 + 0.60629i [/ math], exactamente los números en la solución de Mark Gritter.

Nota 3: El entorno matemático de Quora es realmente molesto.

Muchas buenas respuestas arriba. Algunos códigos C ++ a continuación se basan en las muchas soluciones discutidas anteriormente. Una pregunta similar está disponible en Hackerrank para resolver también: Tutorial en video de Cracking the Coding Interview

// https://www.hackerrank.com/challenges/ctci-recursive-staircase
// Ref: https://github.com/charles-wangkai/hackerrank/blob/master/ctci-recursive-staircase/Solution.java
/ Ref: http://algorithms.tutorialhorizon.com/dynamic-programming-stairs-climbing-puzzle/

#include
#include

// recursividad
int maneras (int n) {
si (n == 1)
retorno 1;
si no (n == 2)
retorno 2;
si no (n == 3)
retorno 4;
más
formas de retorno (n – 1) + formas (n – 2) + formas (n – 3);
}

// no recursivo
int ways2 (int n) {
int ppp = 0, pp = 1, p = 1;
int suma = 0;
para (int i = 0; i suma = ppp + pp + p;
ppp = pp;
pp = p;
p = suma;
}
volver p;
}

// Programación dinámica
int ways3 (int n) {
si (n == 1)
retorno 1;
si no (n == 2)
retorno 2;
si no (n == 3)
retorno 4;
std :: vector tabla (n);
tabla [0] = 1;
tabla [1] = 2;
tabla [2] = 4;
para (int i = 3; i tabla [i] = tabla [i – 1] + tabla [i – 2] + tabla [i – 3];
return table.back ();
}

int main () {
int s;
std :: cin >> s;
para (int i = 0; i int n;
std :: cin >> n;
std :: cout << ways3 (n) << std :: endl;
}
devuelve 0;
}

Es un problema de programación dinámica.
Un niño puede subir a la escalera N desde la escalera N – 1, o la escalera N – 2, o la escalera N -3.
La forma de subir a N es sumar todos los caminos a N – 1, N – 2 y N – 3.
Asi que:
f (n) = f (n – 1) + f (n – 2) + f (n – 3)
Mientras que para las primeras tres escaleras:
f (1) = 1;
f (2) = 1 + f (1)
f (3) = 1 + f (2) + f (1).

En códigos tipo C:
sol [1] = 1;
sol [2] = 2; // 1 + sol [1];
sol [3] = 4; // 1 + sol [2] + sol [1]
para (int i = 4; i <= N; i ++)
sol [i] = sol [i – 1] + sol [i – 2] + sol [i – 3];

Entonces sol [N] será la respuesta.