1. 从棋盘上的“过河马”说起一道经典的动态规划入门题最近在整理蓝桥杯的历年练习题翻到了这道“过河马”。乍一看标题可能会联想到中国象棋里的“马走日”觉得这大概是个简单的路径搜索问题。但当你真正上手去解尤其是当棋盘规模N行M列稍微大一点比如N10 M100时你就会发现简单的DFS深度优先搜索或者BFS广度优先搜索会立刻超时因为状态空间膨胀得太快了。这道题本质上是一个**计数类动态规划DP**的经典入门题它考察的不是你会不会写搜索而是你能不能识别出搜索背后的重叠子问题并用递推的方式高效解决。它就像动态规划世界里的“Hello World”看似简单却包含了状态定义、转移方程、边界处理等所有核心要素。今天我们就来彻底拆解这道ALGO-981不仅告诉你答案怎么来更带你走一遍“为什么这么做”的思考过程让你下次遇到类似的棋盘路径计数问题都能举一反三。2. 问题重述与核心难点分析首先我们得把题目理解透。题目描述通常是在一个N行M列的棋盘上有一个棋子“过河马”。它走的是“日”字形但和象棋不同它只能向右走。也就是说它可以从当前位置(i, j)走到以下几个位置之一假设棋盘左上角为(1,1)向下为i增加向右为j增加(i-2, j1)// 向上两格向右一格(i-1, j2)// 向上一格向右两格(i1, j2)// 向下一格向右两格(i2, j1)// 向下两格向右一格棋子起始于棋盘的最左侧一列的任意一个位置即(i, 1)其中1 i N目标是走到棋盘的最右侧一列即第M列的任意一个位置。我们需要计算一共有多少种不同的行走方案。由于结果可能很大通常要求对某个数比如1000000007取模。核心难点在哪里方向限制只能向右走。这是一个极强的约束它直接决定了我们的状态设计可以简化。既然不能向左那么当我们走到某一列时我们永远不需要回头考虑左边列的状态。这提示我们可以按列进行DP。状态爆炸如果使用DFS/BFS从第一列的N个起点出发每个点有最多4种走法。在M100时路径数量是指数级增长的必然超时。计数而非路径我们不需要输出具体路径只需要方案数。这是动态规划的典型应用场景——利用“记忆化”或“递推”来避免重复计算大量相同子问题的路径数。所以我们的思路很明确放弃搜索采用动态规划。3. 动态规划的状态设计与转移方程推导动态规划的核心就两步定义状态找出状态转移方程。对于棋盘问题最直观的状态就是棋子的坐标(i, j)表示走到第i行第j列这个位置。3.1 状态定义我们定义dp[i][j]表示从第一列的某个起点出发恰好走到位置(i, j)的方案总数。 这里i的取值范围是[1, N]j的取值范围是[1, M]。3.2 转移方程推导“恰好走到(i, j)”这个状态是从哪里来的呢根据“马走日”且只能向右的规则能一步到达(i, j)的点一定位于(i, j)的左边。具体来说有四个可能的“上一个位置”从(i2, j-1)跳过来对应规则4的逆推从(i1, j-2)跳过来对应规则3的逆推从(i-1, j-2)跳过来对应规则2的逆推从(i-2, j-1)跳过来对应规则1的逆推因此dp[i][j]的值应该是这四个来源点的方案数之和。当然前提是这些来源点必须在棋盘范围内。于是我们得到了核心的转移方程dp[i][j] dp[i2][j-1] dp[i1][j-2] dp[i-1][j-2] dp[i-2][j-1]在计算时需要判断每个下标是否在棋盘内1 i N, 1 j M如果越界则该项贡献为0。3.3 初始化边界条件动态规划需要一个起点。我们的起点是第一列j1的所有行。 因此初始化条件为对于所有的i(1 i N)dp[i][1] 1。 这表示从第一列的每个位置出发有一种方案就是不动也算作起点。有的题目可能要求从第一列“开始走”那么起点的方案数就是1。如果题目说从第一列外进入那么初始化可能需要调整但根据常见描述上述初始化是合理的。3.4 最终答案我们需要的是走到最后一列第M列任意位置的总方案数。 所以最终答案ans (dp[1][M] dp[2][M] ... dp[N][M]) % MOD。4. 实现细节、代码结构与避坑指南理论清晰了但实现起来还有不少坑。下面我们一步步拆解。4.1 递推顺序由于状态dp[i][j]依赖于j-1和j-2列的数据我们必须按列j从小到大进行递推。对于每一列j我们再遍历所有行i来计算dp[i][j]。这个顺序保证了当我们计算dp[i][j]时它所需要的j-1和j-2列的数据都已经计算完毕。4.2 边界检查的优雅写法在转移方程中我们需要判断四个来源点是否越界。最直接的方法是写四个if语句。但更简洁高效的方法是在遍历i时只对有效的i进行计算或者使用一个辅助函数来安全地获取dp值如果越界则返回0。 这里提供一个清晰的写法思路MOD 1000000007 dp [[0] * (M 1) for _ in range(N 1)] # 多开一些空间方便下标从1开始 # 初始化第一列 for i in range(1, N 1): dp[i][1] 1 # 按列递推 for j in range(2, M 1): # 从第二列开始 for i in range(1, N 1): total 0 # 检查四个来源点 if i - 2 1 and j - 1 1: total (total dp[i-2][j-1]) % MOD if i - 1 1 and j - 2 1: total (total dp[i-1][j-2]) % MOD if i 1 N and j - 2 1: total (total dp[i1][j-2]) % MOD if i 2 N and j - 1 1: total (total dp[i2][j-1]) % MOD dp[i][j] total # 计算答案 ans 0 for i in range(1, N 1): ans (ans dp[i][M]) % MOD print(ans)4.3 空间优化滚动数组观察转移方程dp[i][j]只依赖于第j-1列和第j-2列的数据。这意味着我们不需要保存整个NM的二维数组只需要保存最近的两列数据即可。这可以将空间复杂度从O(NM)降低到O(N)对于M很大的情况非常有用。我们定义两个一维数组prev1和prev2分别表示前一列(j-1)和前前列(j-2)的所有行的dp值。在计算新的一列curr时根据prev1和prev2来更新。 具体关系是curr[i]来自于prev1[i-2] prev2[i-1] prev2[i1] prev1[i2](注意检查边界) 计算完curr后滚动更新prev2, prev1 prev1, curr。这个优化在面试或竞赛中常被要求它体现了对状态转移本质的深刻理解。实现时务必注意下标的对应关系最好在纸上画一下搞清楚prev1和prev2分别对应的是哪一列。4.4 一个极易忽略的坑大数取模题目结果通常很大要求对10000000071e97一个质数取模。这里有两个关键点在加法过程中就要取模total (total dp[x][y]) % MOD而不是最后才取模。否则中间结果可能溢出即使在Python中虽然整数不限大小但取模操作能保证结果始终在合理范围内并且是题目要求。负数取模在某些语言如C、Java中如果下标计算出现负数直接访问数组会出错。我们通过if判断避免了这个问题。如果使用(i-2N) % N这类循环下标的方式如果题目允许棋盘上下连通则要特别注意取模运算在不同语言中的差异。对于本题明确的边界用if判断最安全。5. 从“过河马”到更一般的路径计数DP解完这道题我们获得的不仅仅是一个答案而是一个解决一类问题的模板。我们可以把思路推广到更一般的情形5.1 状态设计的变体dp[i][j]表示“走到(i,j)的方案数”这是最常用的。有时可以定义dp[i][j]为“从(i,j)走到终点的方案数”此时转移方向是反的初始化在终点列答案求和在第一列。两者是等价的取决于个人习惯。如果题目增加了“不能经过某些障碍格”的条件我们只需在转移前判断(i,j)本身是否是障碍如果是则dp[i][j]恒为0。5.2 转移方程的扩展步长变化如果不是“日”字而是“田”字或其他固定步长只需要修改转移方程中的偏移量即可。方向变化如果可以往左走那么状态转移就可能出现环互相依赖就不能用简单的递推了可能需要用高斯消元或转化为图论问题。本题“只能向右”保证了状态的无后效性是DP能用的前提。维度增加如果棋盘是三维的或者马有更多种跳法原理不变增加状态维度即可。5.3 性能考量时间复杂度我们按列递推每列遍历N行每行计算4次转移所以总时间复杂度是O(N * M * 4)即O(N*M)。对于N, M在1000左右的数据量完全可行。空间复杂度使用滚动数组优化后为O(N)。6. 实测与调试如何验证你的解法理论正确不代表代码正确。对于DP问题尤其是边界复杂的必须进行测试。6.1 小规模数据验证用N2, M3这样的小棋盘手工计算所有路径。然后运行你的程序看结果是否匹配。例如N2, M3。第一列有2个起点(1,1)和(2,1)。从(1,1)出发能走到(2,3)吗检查规则(11, 12) (2,3)可以。所以有一条路径。从(2,1)出发能走到(1,3)吗(2-1, 12) (1,3)可以。所以也有一条路径。总方案数2。用程序跑一下确认输出为2。6.2 中等规模与对拍写一个暴力DFS/BFS函数限制N和M很小比如N5, M6用于生成随机的小规模测试数据对比你的DP程序的结果。两者结果必须完全一致。这是验证DP正确性最有效的方法之一。6.3 特殊边界测试N1时马根本无法移动因为“日”字跳需要至少2行的高度所以只要M1答案应该是0。你的程序能正确处理吗M1时棋子已经在终点列不需要移动。从第一列的N个点出发方案数就是N每个点作为一种方案。你的初始化能得出这个结果吗6.4 关于取模的测试尝试一个较大的N和M比如N10, M10确保你的程序不会因为整数过大而运行异常在Python中问题不大但在C/Java中必须时刻取模。7. 总结与个人心得这道“过河马”题我最初接触时也直接用DFS去写结果当然是不出意外地超时。后来才明白这类“棋盘路径计数”问题只要方向受限尤其是单向性比如只能向右、向下几乎都可以用动态规划来降维打击。我个人在实现时踩过的一个坑是滚动数组的下标对应。一开始没理清prev1和prev2分别代表j-1和j-2列在写转移方程时把来源搞混了导致结果怎么都不对。后来画了一个表格把j,j-1,j-2三列并排标出每个dp[i][j]依赖于前面两列的哪些行一下子就清晰了。所以对于空间优化画图是最直观的调试方法。另一个心得是关于初始化。有些变种题目可能要求马从棋盘外进入第一列那么dp[i][1]就不再是1而是可能从上方或下方跳入。这时初始化可能需要考虑从虚拟的第0列转移过来。理解初始化的物理意义“起点状态”比死记硬背dp[i][1]1更重要。最后动态规划的魅力在于它把指数级的搜索问题变成了多项式级的填表问题。关键就在于识别出“重叠子问题”和“最优子结构”。对于计数问题“最优子结构”往往表现为“到达当前状态的方案数等于所有前驱状态方案数之和”。掌握了这个思维模型再遇到类似的题目比如“过河卒”、“数字三角形”、“不同路径”等等你都能很快地套用并调整。这道题代码不长但涉及的思想是基础且重要的。建议在理解的基础上自己动手实现一遍基础版和滚动数组优化版并用手工和小数据对拍进行验证。把这套流程走通你对动态规划的理解会上一个台阶。