从方格游戏到动态规划：用Python手把手解‘踩方格’问题（附两种递推思路对比）

从方格游戏到动态规划：用Python手把手解‘踩方格’问题（附两种递推思路对比）

想象你站在一个无限延伸的方格矩阵中央，每次移动都会让脚下的格子塌陷。你只能向北、东、西三个方向探索，走过的路会消失无踪。这个看似简单的游戏规则背后，隐藏着动态规划的经典范式——"踩方格"问题。本文将带你用Python重新演绎这道信息学奥赛经典题，从游戏化视角拆解两种递推思路的底层逻辑。

1. 问题建模与游戏规则解析

"踩方格"问题的核心在于理解移动规则与状态约束。让我们先抛开数学公式，用游戏玩家的视角重新定义问题：

• 游戏地图：无限大的二维方格矩阵，起始点为坐标原点(0,0)
• 移动规则：
  • 每次只能向北(↑)、东(→)、西(←)移动一格
  • 不能向南移动，且走过的格子会立即塌陷
• 胜利条件：在n步移动中，找出所有不重复的路径方案

举个例子，当n=2时，所有合法路径如下：

1. (0,0) → (0,1) → (0,2) # 连续向北 2. (0,0) → (0,1) → (1,1) # 北→东 3. (0,0) → (0,1) → (-1,1) # 北→西 4. (0,0) → (1,0) → (1,1) # 东→北 5. (0,0) → (1,0) → (2,0) # 连续东 6. (0,0) → (-1,0) → (-1,1) # 西→北 7. (0,0) → (-1,0) → (-2,0) # 连续西

注意：向东后不能立即向西（反之亦然），因为会回到已塌陷的格子

2. 状态压缩递推法

第一种解法采用状态压缩的思路，将移动方向的信息浓缩到单个状态变量中。我们定义f(n)为走n步的总方案数，通过观察移动模式的规律，可以发现：

• 第n步的方案数取决于前两步的选择
• 关键观察点：
  • 上一步向东/西移动的，当前步有2种选择（继续同向或转向北）
  • 上一步向北移动的，当前步有3种选择（东、西、北）

这种关系可以表示为递推式：

f(n) = 2 * f(n-1) + f(n-2)

对应的Python实现：

def count_paths_compressed(n): if n == 1: return 3 if n == 2: return 7 dp = [0] * (n + 1) dp[1], dp[2] = 3, 7 for i in range(3, n + 1): dp[i] = 2 * dp[i-1] + dp[i-2] return dp[n]

这个解法的优势在于：

• 空间效率高：只需O(n)空间存储中间结果
• 数学直观：直接体现斐波那契类数列的扩展特性
• 计算高效：单层循环，时间复杂度O(n)

3. 状态分离递推法

第二种方法将移动方向的状态显式分离，更适合理解问题本质。我们定义两个状态数组：

• a[n]：第n步向北移动的方案数
• b[n]：第n步向东或西移动的方案数

状态转移规则如下：

1. 向北移动的方案数 = 上一步所有可能移动的方案数（因为从任何方向都可以转向北）

   a[i] = a[i-1] + b[i-1]

2. 向东/西移动的方案数：
   • 上一步向北的，有2种选择（东或西）
   • 上一步向东的，只能继续东或转北（但转北已计入a[i]）
   • 上一步向西的，只能继续西或转北

   b[i] = 2 * a[i-1] + b[i-1]

Python实现：

def count_paths_separated(n): if n == 1: return 3 a = [0] * (n + 1) b = [0] * (n + 1) a[1], b[1] = 1, 2 for i in range(2, n + 1): a[i] = a[i-1] + b[i-1] b[i] = 2 * a[i-1] + b[i-1] return a[n] + b[n]

两种解法的对比：

4. 算法优化与扩展思考

当n>20时，我们需要考虑大数处理和算法优化。Python本身支持大整数运算，但仍有优化空间：

记忆化递归实现：

from functools import lru_cache @lru_cache(maxsize=None) def count_paths_memo(n): if n == 1: return 3 if n == 2: return 7 return 2 * count_paths_memo(n-1) + count_paths_memo(n-2)

矩阵快速幂优化： 将递推式转化为矩阵幂运算，可将时间复杂度降至O(log n)：

def matrix_mult(a, b): return [ [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]], [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]] ] def matrix_pow(mat, power): result = [[1,0], [0,1]] # 单位矩阵 while power > 0: if power % 2 == 1: result = matrix_mult(result, mat) mat = matrix_mult(mat, mat) power //= 2 return result def count_paths_fast(n): if n == 1: return 3 if n == 2: return 7 trans = [[2, 1], [1, 0]] mat = matrix_pow(trans, n-2) return 7 * mat[0][0] + 3 * mat[0][1]

问题变种思考：

1. 如果允许向南移动，状态转移如何变化？
2. 如果每次移动后，不仅当前格子塌陷，相邻格子也有一定概率塌陷？
3. 如果在有限网格中移动（如m×m网格），解法需要如何调整？

5. 可视化与调试技巧

理解递推问题最有效的方式之一是可视化状态转移。我们可以用Python的matplotlib绘制决策树：

import matplotlib.pyplot as plt import networkx as nx def build_decision_tree(n): G = nx.DiGraph() pos = {} level = {} # 添加初始节点 G.add_node("0:3", count=3) pos["0:3"] = (0, 0) level[0] = ["0:3"] for step in range(1, n+1): level[step] = [] for parent in level[step-1]: parent_count = G.nodes[parent]["count"] if step == 1: # 第一步：3种选择 for direction in ["N", "E", "W"]: node = f"{step}:{direction}" G.add_node(node, count=1) G.add_edge(parent, node, direction=direction) pos[node] = (pos[parent][0] + (ord(direction)-78)*0.5, -step) level[step].append(node) else: # 后续步骤根据上一步方向决定 last_dir = parent.split(":")[1][-1] if last_dir == "N": # 上一步向北，当前步3种选择 for direction in ["N", "E", "W"]: node = f"{step}:{parent[2:]}{direction}" G.add_node(node, count=parent_count) G.add_edge(parent, node, direction=direction) pos[node] = (pos[parent][0] + (ord(direction)-78)*0.3, -step) level[step].append(node) else: # 上一步向东/西，当前步2种选择 for direction in ["N", last_dir]: node = f"{step}:{parent[2:]}{direction}" G.add_node(node, count=parent_count) G.add_edge(parent, node, direction=direction) pos[node] = (pos[parent][0] + (ord(direction)-78)*0.3, -step) level[step].append(node) plt.figure(figsize=(12, 8)) nx.draw(G, pos, with_labels=False, node_size=20, arrowsize=10) plt.title(f"Decision Tree for {n} Steps") plt.show()

调试递推算法时，建议：

1. 打印每一步的状态变量值
2. 对小规模n值手工验证结果
3. 比较两种不同递推方法的中间结果
4. 使用断言检查边界条件

# 验证两种方法结果一致 for n in range(1, 21): assert count_paths_compressed(n) == count_paths_separated(n) print(f"n={n}: {count_paths_compressed(n)}")