三角形网格中(0,0)到(2n,0)的迭代式路径总数求解

你要解决的是三角形网格中从(0,0)到(2n,0)的可行路径计数问题，这类路径的核心约束是不能走到j<0的位置（仅i+j为偶数的点存在，j为负时无对应点），每一步只能是向上（j+1）或向下（j-1），总步数为2n，其中恰好n次向上、n次向下——这本质对应第n个卡特兰数。

你的伪代码存在的问题 #

• 逻辑与参数不符：函数参数(i,j)不符合需求（应该传入n），路径数组A的构建逻辑错误，且用全排列枚举路径会产生大量重复（因为有n个相同的1和n个相同的-1），n稍大就会性能爆炸。
• 语法与判断错误：i!是非法写法，前缀和判断sum(A[1:i]) < 0逻辑错误（应该检查每一步的累计和都≥0），集合操作set.append(path)不符合语法。
• 效率极低：全排列的复杂度是O((2n)!)，完全不适合n≥5的场景。

正确的迭代实现（动态规划） #

这种方法通过状态转移直接计数，避免枚举所有路径，效率更高：

def count_paths(n):
    # dp[h] 记录当前步数下，到达高度h的路径数量
    dp = {0: 1}  # 初始状态：0步，在高度0，路径数为1
    
    for _ in range(2 * n):
        next_dp = {}
        for current_h, path_count in dp.items():
            # 向上走一步，到达current_h + 1
            next_h = current_h + 1
            next_dp[next_h] = next_dp.get(next_h, 0) + path_count
            
            # 向下走一步，只有当前高度>0时才合法（避免走到j=-1）
            if current_h > 0:
                next_h = current_h - 1
                next_dp[next_h] = next_dp.get(next_h, 0) + path_count
        
        dp = next_dp
    
    # 返回2n步后到达高度0的路径总数
    return dp.get(0, 0)

更高效的迭代实现（卡特兰数公式） #

因为问题本质是卡特兰数，我们可以直接用卡特兰数的递推公式迭代计算，时间复杂度O(n)，空间复杂度O(1)：

def count_paths_catalan(n):
    catalan = 1
    for i in range(1, n + 1):
        catalan = catalan * (4 * i - 2) // (i + 1)
    return catalan

内容的提问来源于stack exchange，提问作者CWT_Simon