Project Euler第15题求解程序仅支持小于12的数值，如何修复？

首先回顾问题：

从2×2网格的左上角出发，仅向右或向下移动（不回溯）到右下角共有6条路径。求20×20网格中的路径总数？

你现有的递归+缓存思路方向是对的，但代码存在逻辑错误和效率问题，导致无法计算20×20的情况，下面我们一步步解决：

现有代码的问题分析 #

• 边界条件逻辑错误：当y == 1时，代码直接访问table[left_pos]，但该键可能尚未被初始化（比如计算find_cost(2,1)时，left_pos是"11"，此时字典中没有这个键），会触发KeyError，这是导致较大数值无法计算的直接原因。
• 键的选择低效：用字符串拼接str(x)+str(y)作为字典键，不如直接使用元组(x,y)直观且高效。
• 递归开销：自顶向下的递归对于20×20的规模虽然不会栈溢出，但相比迭代式动态规划，额外开销更大。

解决方案 #

我们提供三种可行的解决方法，从修复原代码到更高效的数学方法：

方法一：修复并优化递归+缓存代码 #

修正边界条件，改用元组作为键，确保逻辑正确：

table = {}

def find_cost(x, y):
    # 边界条件：当x=0或y=0时，只有1条路径（一直走右或一直走下）
    if x == 0 or y == 0:
        return 1
    current_pos = (x, y)
    if current_pos in table:
        return table[current_pos]
    # 递归计算上方和左方的路径数并缓存
    table[current_pos] = find_cost(x - 1, y) + find_cost(x, y - 1)
    return table[current_pos]

# 计算20×20网格的路径数（终点坐标为(20,20)，起点为(0,0)）
print(find_cost(20, 20))

方法二：迭代式动态规划（推荐，高效且无递归开销） #

创建二维数组，从边界开始逐步填充，避免递归带来的额外开销：

n = 20
# 创建(n+1)×(n+1)的二维数组，初始化为0
dp = [[0]*(n+1) for _ in range(n+1)]

# 边界条件：第一行和第一列的路径数都是1（只能沿单一方向走）
for i in range(n+1):
    dp[i][0] = 1
    dp[0][i] = 1

# 填充数组：每个位置的路径数=上方位置路径数+左方位置路径数
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

print(dp[n][n])

方法三：数学方法（最简洁高效） #

这个问题本质是组合数学问题：从左上角到右下角需要走20次向右和20次向下，总共40步，路径总数就是从40步中选择20步走向右（剩下的20步走向下）的组合数，公式为：
$$C(40,20) = \frac{40!}{20! \times 20!}$$

用Python计算这个组合数非常简单，我们可以用内置函数或手动计算（Python的整数支持任意精度，不用担心溢出）：

import math

# 直接计算组合数C(40,20)（Python 3.10+支持）
print(math.comb(40, 20))

兼容旧Python版本的手动计算版本：

def combination(n, k):
    result = 1
    # 简化计算：避免直接计算大数阶乘，逐步乘除
    for i in range(1, k+1):
        result = result * (n - k + i) // i
    return result

print(combination(40, 20))

结果验证 #

20×20网格的路径总数是137846528820，三种方法都能得到这个结果。

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