Определите, сколько разных массивов возможно

Question

Предположим, у нас есть логический массив длины X. Единственное правило: TRUE не должно встречаться дважды в соседних местах.Особенно разрешен массив только с ложными значениями.Например, это запрещено: [1,1,0,0,0] и допускается: [1,0,0,0,0], [0,0,0,0,0], [1,0,1,0,1] и т. Д. Как я могу использовать динамическое программирование, чтобы определить, сколько существует различных допустимых массивов длины X?

Answer 1

Вам не нужно динамическое программирование.Для длины массива X число допустимых массивов равно Fib (X + 1), где Fib - массив чисел Фибоначчи.

X = 1: допустимые массивы: 2

X = 2:допустимые массивы: 3

X = 3: допустимые массивы: 5

X = 4: допустимые массивы: 8

и т. д. *

Демонстрация:

Давайте предположим, что мы ищем массивы для X, и мы знаем количество допустимых массивов для X-1.Мы можем свободно добавлять ноль в конец каждого из этих массивов длины X-1, так что пока это F (X-1).Мы также можем добавить '1' в конец каждого массива X-1, который заканчивается 0. Но сколько из этих массивов?Ну, это точно F (X-2), потому что мы могли бы сгенерировать массивы длины X-1 с нулевым окончанием точно таким же образом: добавив ноль в конце каждого массива длины X-2.Итак, F (X) = F (X-1) + F (X-2) И это в точности определение массива Фибоначчи.

Все, что нам нужно сделать, - это вручную вычислить первые два элемента, чтобы определить,это в точности массив Фибоначчи или он сдвинут.

Вы даже можете найти формулу для вычисления N-го элемента массива Фибоначчи, чтобы ее можно было решить в O (1).

Answer 2

Пусть T _i будет числом массивов длины i , которые соответствуют вашему критерию и заканчиваются на 1, ипусть F _i будет числом массивов длины i , которые соответствуют вашему критерию, и not заканчивается1.

Тогда:

• T ₀ = 0
• F ₀ = 1
• T _{i + 1} = F _я .(Каждый массив длины i + 1, который соответствует вашему критерию и заканчивается на 1, состоит из массива длины i , который соответствует вашему критерию и соответствует , а не конец в 1, плюс дополнительный 1 в конце.)
• F _{i + 1} = F _i + T _i .(Каждый массив длины i + 1, который соответствует вашему критерию и не заканчивается в 1, состоит из массива длины i , который соответствует вашему критерию,плюс еще 0 в конце.)
• Вы хотите F _X + T _X .

Таким образом, вы можете просто написать цикл, который вычисляет F _i и T _i для каждого i от 0 до X , а затем возврат F _X + T _X .

(Это даже не динамическое программирование,по сути, потому что вам не нужно хранить частичные значения; F _{i + 1} и T _{i + 1} зависит только от F _i и T _i . Так что это O ( X ) время и O (1) пробел.)

Answer 3

Решение dp будет иметь два параметра состояния.Одна - это позиция массива, а другая - значение предыдущей позиции.Если значение предыдущей позиции равно 1, тогда вы можете выбрать только 0. Если значение предыдущей позиции равно 0, тогда вы можете выбрать либо 1, либо 0. Надеюсь, это поможет.

Answer 4

Я думаю, что вы можете рассчитать число без использования DP.Поскольку вы знаете общее количество массивов для длины N, то есть `2 ^ N '.

Теперь вам нужно вычесть те bad массивы, которые не соответствуют критериям, если они имеют смежные 1.Для массива длины N существуют следующие случаи

1. the array has no 1's, only one case, and it is a valid array
2. the array has one 1's, all cases are valid
3. the array has two 1's, there are N - 1 cases which are not valid
4. the array has three 1's, there are (N-1) * (N-2) / 2 cases which are not valid

...