如何找到整数1,2,3可以加起来n的方式？

Question

给定一组整数1,2和3,找出这些可以加起来的方式的数量.(顺序很重要,即说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数字(Fibonacci数字的变体):

可以编写一个简单的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)