He encontrado este interesante problema de programación dinámica y quiero conocer el enfoque.

Se nos da una matriz 'a' de tamaño-'n '.

Cada elemento de la matriz es '1' o '2'.

Comenzamos en el índice '0'. Si a [i] = 1, podemos ir a i + 1 o i-1.

or el contrario, si a [i] = 2, podemos ir a i + 1 o i + 2 o i-1 o i-2.

Tenemos que encontrar el número de todas las rutas posibles.

** Restricción principal **: - 1) Podemos ir a un índice particular en una matriz solo una vez.

2) Siempre comenzamos en el índice '0'.

3) Una ruta puede terminar en cualquier momento que queramos: -)

Matriz de ejemplo: -> [1,1,1,1]

Respuesta: - 4

1a ruta posible: [0]

2ND ruta posible: [0,1]

3.er camino posible: [0,1,2]

4ta ruta posible: [0,1,2,3]

Otro ejemplo :

[2,2,2]

Respuesta: - 5

Paths: - [0], [0,1], [0,1,2], [0,2,1], [0,2].

(¡Esta pregunta se divide en 3 partes!)

Valor (s) de n están en el rango: - 1) [1,100000]

                            2) [1,10]

                             3)[1,1000]