思路 这个问题要求计算在无限方格矩阵上行走n步的不同方案数，每次只能向北、东、西三个方向移动，且走过的格子不能重复。通过动态规划的思路，我们可以将状态分为三个方向：北（N）、东（E）、西（W）。每一步的选择取决于前一步的方向，从而避免重复路径。 状态定义：设 prev_N、prev_E、prev_W 分别表示上一步向北、东、西方向移动的方案数。 状态转移： current_N（当前向北）：可以从任何方向转移而来。 current_E（当前向东）：只能从北或东转移而来。 current_W（当前向西）：只能从北或西转移而来。 初始状态：当 n=1 时，三个方向各有1种方案。 递推计算：通过循环递推每一步的状态，直到计算到第n步。