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

Question

这个问题与this有关和 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

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