计算锯齿形序列

Question

之字形序列是一个每一个元素都比它的相邻元素少或多的序列：1 3 2和{}是锯齿形，1 2 3和{}不是。在

给定两个数n，k求出从数字1..k可以生成多少个大小为n的序列

例：n=3k=3答案：10

121、212、131、313、232、323、132、231、312、213（无需生成，仅为清晰起见）

我想到了这个解决方案。请告诉我是否可以做得更好。在

import sys

ZAG = {}
ZIG = {}

def zag(n, i):
    result = 0

    for j in xrange(1, i):    
        if (n - 1, j) not in ZIG:
            ZIG[(n - 1, j)] = zig(n - 1, j)
        result += ZIG[(n - 1, j)]

    return result    

def zig(n, i):
    result = 0

    for j in xrange(i + 1, MAX_NUMBER + 1):
        if (n - 1, j) not in ZAG:
            ZAG[(n - 1, j)] = zag(n - 1, j)
        result += ZAG[(n - 1, j)]

    return result

def count(n): 
    if n == 1:
        return MAX_NUMBER

    result = 0

    for i in xrange(1, MAX_NUMBER + 1):
        ZIG[(1, i)] = 1
        ZAG[(1, i)] = 1

    for i in xrange(1, MAX_NUMBER + 1):
        result += 2*zag(n, i)

    return result

def main(argv):
    global MAX_NUMBER
    MAX_NUMBER = int(argv[1])
    print count(int(argv[0]))

if __name__ == "__main__":
    main(sys.argv[1:])

Answer 1

如果通过递归调用Zig（值小于上一个数字）和Zag（值大于上一个数字）循环调用生成序列，它会变得更好一些，并且可以通过将已解决的子问题存储在静态表中而使其更好（计算方面，而不是内存方面）。在

Answer 2

整个序列中的顺序是以前两个元素的顺序给出的。有两种排序方式：上下向上。。。从上到下-。。。两种顺序的序列数目相同，因为一种顺序的序列可以通过将每个数x与{}交换而转换成另一种顺序。在

设U_k(n)是长度为n的序列数。设U_k(n, f)是长度为n且第一个数为f的序列数。类似的定义D_k(n)和{}。在

那么长度为n（对于n>1）的序列数为：

U_k(n) + D_k(n) = 2*U_k(n) = 2*( sum U_k(n, f) for f in 1 ... k ).

同样的论点给出：

^{pr2}$

编辑：

稍微简单一点的实现。M(n,k)返回第n行（从后面），并且C(n,k)计算序列数。在

def M(n, k):
    if n == 1: return [1]*k
    m = M(n-1, k)
    return [sum(m[:i]) for i in xrange(k)][::-1]

def C(n, k):
    if n < 1: return 0
    if n == 1: return k
    return 2*sum(M(n,k))