骑士拨号器算法求助：递归记忆化解法大n值下结果异常

问题描述 #

基于国际象棋骑士的L形移动规则，计算长度为n的有效电话号码总数。采用带记忆化递归实现，但当n=3131时输出结果为4，与预期的136006598不符，代码如下：

class Solution:
    def knightDialer(self, n: int) -> int:
        dp = {}
        def traverse(r, c, length):
            if r < 0 or r > 3 or c < 0 or c > 2 or keypad[r][c] == 0:
                return 0
            if length == n:
                return 1
            if (r,c,length) in dp:
                return dp[(r,c,length)]
            row = [-2,-2,-1,1,2,2,1,-1]
            col = [-1,1,2,2,1,-1,-2,-2]
            count = 0
            for pos in range(8):
                nrow = r+row[pos]
                ncol = c+col[pos]
                count += traverse(nrow, ncol, length + 1)
            dp[(r,c,length)] = count
            return count
        keypad = [[1,1,1],[1,1,1],[1,1,1],[0,1,0]]
        ans = 0
        for r in range(4):
            for c in range(3):
                ans += traverse(r,c,1)
        return ans%(10^9+7)

问题根源 #

1. 模运算符号错误：Python中^是按位异或运算符，不是幂运算。正确的10^9+7应该写成10**9+7，错误的模运算会导致结果完全偏离预期。
2. 递归深度超限：当n=3131时，递归深度达到3131，远超Python默认的递归深度限制（约1000），触发栈溢出异常后程序返回错误结果。
3. 大n下记忆化效率低：字典存储状态的开销较高，对于n=3131这种大数值，会导致计算缓慢甚至异常。

修复方案 #

改用迭代式动态规划，避免递归深度问题，同时修正模运算：

class Solution:
    def knightDialer(self, n: int) -> int:
        MOD = 10**9 + 7
        # 每个数字对应的可达数字列表（索引对应数字0-9）
        jumps = [
            [4,6],      # 0
            [6,8],      # 1
            [7,9],      # 2
            [4,8],      # 3
            [0,3,9],    # 4
            [],         # 5（骑士无法从5跳到任何有效数字）
            [0,1,7],    # 6
            [2,6],      # 7
            [1,3],      # 8
            [2,4]       # 9
        ]
        # dp[num] 表示当前长度下，以num结尾的有效号码数量
        dp = [1]*10  # 长度为1时，每个数字都有1种可能
        for _ in range(1, n):
            new_dp = [0]*10
            for num in range(10):
                for next_num in jumps[num]:
                    new_dp[next_num] = (new_dp[next_num] + dp[num]) % MOD
            dp = new_dp
        return sum(dp) % MOD

说明 #

1. 修正了模运算符号，使用10**9+7替代错误的10^9+7
2. 采用迭代式动态规划，彻底避免递归深度超限问题，同时大幅提升计算效率
3. 预先整理每个数字的可达数字列表，简化状态转移逻辑，减少无效判断

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