Как узнать количество возможных способов добавления 1 2 и 3 к данной сумме, избегая повторения? - PullRequest
Новая
       27

Как узнать количество возможных способов добавления 1 2 и 3 к данной сумме, избегая повторения?

1 голос
/ 14 апреля 2019

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

Повторите вопрос

ИтакЯ хочу выяснить количество возможных способов добавления 1, 2 и 3 к N. Решение можно вычислить с помощью рекурсивной формулы F[n] = F[n-1] + F[n-2] + F[n-3], где F[0] = 1, F[1] = 1, F[2] = 2.Конечно, используя динамическое программирование, я могу решить его за линейное время.

Мое ограничение

Ограничение: в результирующей последовательности не должно быть двух элементов, повторяющихся подряд .
Таким образом, для N = 4 результат может быть [[1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [3, 1], [1, 1, 2], [2, 2], [1, 3]], но 1 1 1 1, 2 1 1, 1 1 2 и 2 2 запрещены, поэтому применение ограничения F[4] становится 3.

Может кто-нибудь сказать, как будет выглядеть рекурсивная формула для этой задачи?Или, может, у кого-то есть идея получше?

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

Ответы [ 2 ]

1 голос
/ 14 апреля 2019

Пусть F1, F2, F3 - количество способов построения N из 1, 2 и 3, не начиная с 1, 2, 3 соответственно.

Тогда: 

F1(N) = F2(N-2) + F3(N-3)
F2(N) = F1(N-1) + F3(N-3)
F3(N) = F1(N-1) + F2(N-2)

с граничными условиями: 

F1(0) = F2(0) = F3(0) = 1
F1(x) = F2(x) = F3(x) = 0 (for x < 0)

Затем для решения исходной задачи: F(0) = 1, F(N) = F1(N-1) + F2(N-2) + F3(N-3)

Линейное решение, использующее O (1) пробел: 

def F(N):
    a, b, c, d, e, f, g, h, i = 1, 0, 0, 1, 0, 0, 1, 0, 0
    for _ in range(N-1):
        a, b, c, d, e, f, g, h, i = e+i, a, b, a+i, d, e, a+e, g, h
    return a+e+i

for n in range(11):
    print(n, F(n))

При этом используются следующие рекуррентные отношения: 

F1(i+1), F1(i), F1(i-1) = F2(i-1)+F3(i-2), F1(i), F1(i-1)
F2(i+1), F2(i), F2(i-1) = F1(i)+F3(i-2), F2(i), F2(i-1)
F3(i+1), F3(i), F3(i-1) = F1(i)+F2(i-1), F3(i), F3(i-1)

Это дает вам возможность построить Fn (i + 1), Fn (i), Fn (i).-1) из Fn (i), Fn (i-1), Fn (i-2) так же, как работает обычный алгоритм Фибоначчи с линейным временем (построение Fib (n + 1), Fib (n) из Fib(n), Fib (n-1)).Эти рекуррентные отношения кодируются в строке, которая обновляет переменные a до i.

1 голос
/ 14 апреля 2019

Ну, все, что вам нужно сделать, это добавить еще одно измерение к классическому решению Фибоначчи.

Итак, dp [n] [x] - количество возможных способов получить некоторые числа 1,2,3, чтобы их сумма равнялась n, и у них не было элементов, повторяющихся в строке

базовый случай прост, просто выберите какой-то неиспользуемый элемент (т. Е. 0) и задайте его как один из способов получить сумму 0.

Итак, дп [0] [0] = 1

Теперь просто заполните таблицу ДП 

const int n = 4;
    int dp[n+5][5] = {};
    dp[0][0] = 1;

    for(int i=0; i<=n; i++) //current sum
        for(int j=1; j<=3; j++) //what we use now to extend sum
            for(int k=0; k<=3; k++) //last used
            if(j!=k) //we cant use same as last
            dp[i+n][j]+=dp[i][k];

    cout<<dp[n][1]+dp[n][2]+dp[n][3]; //our sequence could end in any of 1,2,3 so just sum it up

Сложность O (n)

...