在三角形网格中查找路径总数(无递归迭代)

Question

我有一个给定的三角形网格：

三角形

对于i+j为偶数的每个点(i，j)：

给定递归函数

现在我需要写一个迭代函数，它找到从(0,0)到点(2n，0)的所有可能路径，给定n∈n。

所以我的想法，用伪代码写的：

def path (i,j):

paths = set()
A = [ 1 for  x in range(j)]

for x in range (i - len(A)):
A.append (last)-(-1)
A.append (-1)
set.append(path)

for i in range (i!):
candidate = permutate(A)
for i in range(len(A)):
if sum (A [1: i]) < 0
break
Paths.append(candidate)
return len(paths)

我需要计算可能到达(2n，0)的路径总数

Answer 1

从更数学的角度来看，这个问题相当于一个更著名的问题——平衡括号。每个步骤up-right是(，每个步骤down-right是)，有n个括号对，有多少个有效的括号序列？

n的答案是第n个加泰罗尼亚数，即nck(2n, n) - nck(2n, n+1)(nck是"n选择k")。在python中，这是-

from math import comb
def catalan(n):
return comb(2*n, n) - comb(2*n, n+1)

因此，"；通过我的三角形网格，从(0，0)到(2n，0)有多少不同的最短路径"为CCD_ 10。

Answer 2

对于除(0,0)以外的每个节点，到达该节点的方式数是满足其直接上级的方式数的总和。有一种方法可以达到(0,0)。

从(0,0)开始->1和包含(1，1)的队列。在每次迭代中，取队列前面的节点，将其更新为其前置节点的总和，并将所有前置节点都已计算的任何后续节点添加到队列的末尾。

(0,0) -> 1; queue = [(1,1)]
(1,1) -> 1; queue = [(2,2), (2,0)]
(2,2) -> 1; queue = [(2,0), (3,3)]
(2,0) -> 1; queue = [(3,3), (3,1)]
(3,3) -> 1; queue = [(3,1), (4,4)]
(3,1) -> 2; queue = [(4,4), (4,0), (4,2)]
... and so on

Answer 3

import math
A = []
def C_iterativ(n):
C = [[0 for _ in range(n+2)] for _ in range(2*n+1)]
C[0][0] = 1
for i in range(2*n+1):
for j in range(n+1):
C[i][j] += C[i-1][j-1] + C[i-1][j+1]
return C[2*n][0]
for i in range(20):
print(int(1/(i+1)*math.factorial(2*i)/(math.factorial(i)**2)) == C_iterativ(i))

---

递归解决方案：

def C_memo(i, j, memo={}):
if (i, j) in memo:
return memo[(i, j)]
if i == j == 0:
result = 1
elif i == 0 and j > 0:
result = 0
elif i > 0 and j == 0:
result = C_memo(i-1, 1, memo)
elif i > 0 and j > 0:
result = C_memo(i-1, j-1, memo) + C_memo(i-1, j+1, memo)
memo[(i, j)] = result
return result

---

_{此答案发布为OP CWT_Simon在CC by-SA 4.0下对"在三角形网格中查找路径总量(无递归迭代)"问题的编辑。}