algorithm - 三角形中的路径数

Question

我最近遇到了这个问题的一个更困难的变体，但意识到我无法为这个非常简单的案例生成解决方案。我搜索了 Stack Overflow，但找不到以前回答此问题的资源。

给定一个三角形 ABC，您必须计算从“A”开始到“A”结束的一定长度的路径数。假设我们的函数 f(3) 被调用，它必须返回从 A 开始和结束的长度为 3 的路径数:2 (ABA,ACA)。

我在制定优雅的解决方案时遇到问题。现在，我已经编写了一个生成所有可能路径的解决方案，但对于更大的长度，该程序太慢了。我知道一定有一个很好的动态编程解决方案可以重用我们之前计算过的序列，但我不太明白。非常感谢所有帮助。

我的愚蠢代码:

def paths(n,sequence):
    t = ['A','B','C']
    if len(sequence) < n:
        for node in set(t) - set(sequence[-1]):
            paths(n,sequence+node)
    else:
        if sequence[0] == 'A' and sequence[-1] == 'A':
            print sequence

Answer 1

设 PA(n) 是从 A 回到 A 的路径数，正好是 n 步。 设 P!A(n) 是从 B(或 C)到 A 的路径数，正好是 n 步。

然后:

PA(1) = 1
PA(n) = 2 * P!A(n - 1)

P!A(1) = 0
P!A(2) = 1
P!A(n) = P!A(n - 1) + PA(n - 1)
       = P!A(n - 1) + 2 * P!A(n - 2) (for n > 2) (substituting for PA(n-1))

我们可以解析地求解 P!A 的差分方程，就像我们求解 Fibonacci 一样，注意 (-1)^n 和 2^n 都是差分方程的解，然后找到系数 a、b 这样P!A(n) = a*2^n + b*(-1)^n。

我们最终得到等式 P!A(n) = 2^n/6 + (-1)^n/3，而 PA(n) 为 2^(n-1)/3 - 2(- 1)^n/3.

这给了我们代码:

def PA(n):
    return (pow(2, n-1) + 2*pow(-1, n-1)) / 3

for n in xrange(1, 30):
    print n, PA(n)

给出输出:

1 1
2 0
3 2
4 2
5 6
6 10
7 22
8 42
9 86
10 170
11 342
12 682
13 1366
14 2730
15 5462
16 10922
17 21846
18 43690
19 87382
20 174762
21 349526
22 699050
23 1398102
24 2796202
25 5592406
26 11184810
27 22369622
28 44739242
29 89478486