python - 如何找到整数 1,2,3 加起来等于 n 的方式数？

Question

给定一组整数 1、2 和 3，找出这些整数加起来等于 n 的方式的数量。 (顺序很重要，也就是说 n 是 5。1+2+1+1 和 2+1+1+1 是两个不同的解决方案)

我的解决方案涉及将 n 拆分为 1 的列表，因此如果 n = 5，则 A = [1,1,1,1,1]。我将通过添加相邻数字从每个列表递归地生成更多子列表。因此 A 将生成另外 4 个列表:[2,1,1,1]、[1,2,1,1]、[1,1,2,1]、[1,1,1,2]，每个这些列表中的一部分将生成更多的子列表，直到它到达像 [3,2] 或 [2,3] 这样的终止情况

这是我提出的解决方案(在 Python 中)

ways = []
def check_terminating(A,n):
    # check for terminating case
    for i in range(len(A)-1):
        if A[i] + A[i+1] <= 3:
            return False # means still can compute
    return True

def count_ways(n,A=[]):
    if A in ways:
       # check if alr computed if yes then don't compute
       return True
    if A not in ways: # check for duplicates
        ways.append(A) # global ways
    if check_terminating(A,n):
        return True # end of the tree
    for i in range(len(A)-1):
        # for each index i,
        # combine with the next element and form a new list
        total = A[i] + A[i+1]
        print(total)
        if total <= 3:
            # form new list and compute
            newA = A[:i] + [total] + A[i+2:]
            count_ways(A,newA)
            # recursive call

# main            
n = 5
A = [1 for _ in range(n)]

count_ways(5,A)
print("No. of ways for n = {} is {}".format(n,len(ways)))

我可以知道我是否在正确的轨道上吗？如果是这样，有什么方法可以使这段代码更有效率吗？

请注意，这不是硬币找零问题。在硬币找零中，出现的顺序并不重要。在我的问题中，1+2+1+1 与 1+1+1+2 不同，但在硬币找零中，两者是相同的。请不要为这个答案发布硬币找零解决方案。

编辑:我的代码可以正常工作，但我想知道是否有更好的解决方案。感谢您的帮助:)

Answer 1

递推关系为F(n+3)=F(n+2)+F(n+1)+F(n) 其中F(0)=1, F(-1)=F(-2 )=0。这些是 tribonacci 数(斐波那契数的变体):

可以编写一个简单的 O(n) 解决方案:

def count_ways(n):
    a, b, c = 1, 0, 0
    for _ in xrange(n):
        a, b, c = a+b+c, a, b
    return a

它更难，但可以用相对较少的算术运算来计算结果:

def count_ways(n):
    A = 3**(n+3)
    P = A**3-A**2-A-1
    return pow(A, n+3, P) % A

for i in xrange(20):
    print i, count_ways(i)