ел эту интересную проблему динамического программирования и хочу знать подход.

Нам дан массив 'a' размера -n.

Каждый элемент массива имеет значение «1» или «2».

Мы начинаем с индекса «0». Если a [i] = 1, мы можем перейти к i + 1 или i-1.

Напротив, если a [i] = 2, мы можем перейти к i + 1 или i + 2 или i-1 или i-2.

Мы должны найти количество всех возможных путей.

** Основное ограничение **: - 1) Мы можем перейти к определенному индексу в массиве только один раз.

2) Мы всегда начинаем с индекса -0.

3) Путь может закончиться в любое время, когда мы захотим: -)

Пример массива: -> [1,1,1,1]

Ответ: - 4

1-й возможный путь: [0]

2-й возможный путь: [0,1]

3-й возможный путь: [0,1,2]

4-й возможный путь: [0,1,2,3]

Другой пример : -

[2,2,2]

Ответ: - 5

Пути: - [0], [0,1], [0,1,2], [0,2,1], [0,2].

(Этот вопрос делится на 3 части!)

Значения n находятся в диапазоне: - 1) [1 100 000]

                            2) [1,10]

                             3)[1,1000]