和为N的加法算式

5 = 1 + 1 + 1 + 1 + 1
  = 1 + 1 + 3
  = 1 + 3 + 1
  = 3 + 1 + 1
  = 1 + 4
  = 4 + 1

此题与找零问题的不同点在于顺序，比如1+4和4+1算两种不同的加法算式。找零问题求的是组合，此问题求的是排列。相同点是，每个元素都可以无限使用。

def n_sum(n: int, comp: list[int]) -> int:
    if n == 0:
        return 1
    if n < 0:
        return 0
    w = []
    for i in comp:
        w.append(n_sum(n-i,comp))
    return sum(w)


assert n_sum(1,[1,3,4]) == 1
assert n_sum(2,[1,3,4]) == 1
assert n_sum(3,[1,3,4]) == 2
assert n_sum(4,[1,3,4]) == 4
assert n_sum(5,[1,3,4]) == 6

print('n=10:', n_sum(10,[1,3,4]))
print('n=20:', n_sum(20,[1,3,4]))
print('n=30:', n_sum(30,[1,3,4]))

n=10: 64
n=20: 7921
n=30: 974169

思路：假设P(5)表示和为5时的排列数，那么P(5) = P(5-1) + P(5-3) + P(5-4)，即P(5)等于先使用1的排列数，加上先用3的排列数，加上先用4的排列数。先用的数不一样，排列一定不一样。（从上到下划分子问题）

这个递归算法的复杂度是指数级的！N稍微大一点，就算不出来了......上面这段代码，属于multi-recursive（递归调用在一个for循环内），重复计算太多了，需要用DP的思路来优化！

comp = [1,3,4]
def n_sum_2(n: int) -> int:
    p = [1]
    if n == 1:
        return 1
    p.append(1)
    if n == 2:
        return 1
    p.append(1)
    if n == 3:
        return 2
    p.append(2)
    for i in range(4,n+1):
        p.append(p[i-1] + p[i-3] + p[i-4])
    return p[-1]

这个非recursive的DP版本，超级快！！用肉眼看看代码就能识别出来快的味道...

def n_sum_d(n: int, comp: list[int]) -> list[tuple[int,...]]:
    if n == 0:
        return [()]
    if n < 0:
        return []
    w = []
    for i in comp:
        w += [z+(i,) for z in n_sum(n-i,comp)]
    return w


assert len(n_sum_d(1,[1,3,4])) == 1
assert len(n_sum_d(2,[1,3,4])) == 1
assert len(n_sum_d(3,[1,3,4])) == 2
assert len(n_sum_d(4,[1,3,4])) == 4
assert len(n_sum_d(5,[1,3,4])) == 6

from pprint import pprint
print('6:')
pprint(n_sum_d(6,[1,3,4]))

6:
[(1, 1, 1, 1, 1, 1),
 (3, 1, 1, 1),
 (1, 3, 1, 1),
 (4, 1, 1),
 (1, 1, 3, 1),
 (1, 4, 1),
 (1, 1, 1, 3),
 (3, 3),
 (1, 1, 4)]

当一层层递归调用最后得到n==0时，出现一个[()]，然后一层层返回，将每一层使用的数字加到这个tuple里面。如果最后得到的是n!=0，出现[]，一层层返回，listcomp都是空，最后就不会加入w。

comp = [1,3,4]
def n_sum_d2(n: int) -> list[tuple[int,...]]:
    p = [[()]]
    if n == 1:
        return [(1,)]
    p.append([(1,)])
    if n == 2:
        return [(1,1)]
    p.append([(1,1)])
    if n == 3:
        return [(1,1,1),(3,)]
    p.append([(1,1,1),(3,)])
    for i in range(4,n+1):
        """
        p = p[-4:]
        u1 = [z+(1,) for z in p[-1]]
        u3 = [z+(3,) for z in p[-3]]
        u4 = [z+(4,) for z in p[-4]]
        """
        u1 = [z+(1,) for z in p[i-1]]
        u3 = [z+(3,) for z in p[i-3]]
        u4 = [z+(4,) for z in p[i-4]]
        p.append(u1+u3+u4)
    return p[-1]

assert len(n_sum_d2(1)) == 1
assert len(n_sum_d2(2)) == 1
assert len(n_sum_d2(3)) == 2
assert len(n_sum_d2(4)) == 4
assert len(n_sum_d2(5)) == 6
assert len(n_sum_d2(30)) == 974169

from pprint import pprint
print('6:')
pprint(n_sum_d2(6))

注释掉的那几行，是另一个小改动：其实不需要一直保存整个计算过程的所有内容，只需要保存最近4个计算结果即可继续计算下去，内存更友好！