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

Question

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

Repeat the question

所以，我想找出向N添加1,2和3的可能方法的数量。解决方案可以使用递归公式F[n] = F[n-1] + F[n-2] + F[n-3]计算，其中F[0] = 1，F[1] = 1，F[2] = 2。当然，使用动态编程我可以在线性时间内解决它。

My restriction

限制是：结果序列必须没有连续重复的两个元素。 因此，对于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

让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）空间的线性时间解决方案：

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的行中。

Answer 2

那么你需要做的就是为经典的fibonacci dp解决方案增加一个维度。

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

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

所以dp [0] [0] = 1

现在只需填写dp表

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）