如何找出将 1 2 和 3 添加到给定总和避免重复的可能方法的数量？

Question

这个问题与 and this one有关，但我想在这里做一些限制。

重复问题

所以，我想找出将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.

谁能说出这个问题的递归公式是什么样子的？或者也许有人有更好的主意？

我在这里发布这个问题，因为它与动态规划有关，与数学和组合数学无关。

Answer 1

好吧，您需要做的就是为经典斐波纳契 dp 解决方案增加一维。

所以 dp[n][x] - 获得一些数字 1,2,3 的可能方法的数量使得它们的总和为 n 并且它们没有连续重复的元素

基本情况很简单，只需选择一些未使用的元素（即 0）并将其设置为求和为 0 的一种方法。

所以 dp[0][0] = 1

现在补dp就行了table

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)

Answer 2

令F1、F2、F3分别为从1、2、3构造N的方法数，而不是分别从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) 的线性时间解决方案 space:

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)、Fn(i-1)、Fn(i-2) 构造 Fn(i+1)、Fn(i)、Fn(i-1) 的方法与通常的线性时间 Fibonacci 算法的工作方式相同（从 Fib(n)、Fib(n-1) 构造 Fib(n+1)、Fib(n)）。这些递归关系被编码在将变量 a 更新为 i.

的行中

如何找出将 1 2 和 3 添加到给定总和避免重复的可能方法的数量？

How to find out the number of possible ways of adding 1 2 and 3 to given sum avoiding repetition?

algorithm

dynamic-programming

fibonacci

重复问题

我的限制