青蛙受限移动路径计数的DP建模咨询

问题背景 #

一只青蛙从点A $(0,0)$ 移动到点B $(5,6)$，每一步只能向右移动1单位或者向上移动1单位，但青蛙拒绝连续三次朝同一个方向移动。请求解青蛙从A到B的路径总数。

用户疑问 #

我现在有个困惑：这个问题需要用3维DP来解决吗？
如果去掉“不能连续三次朝同一方向移动”的限制条件，我知道可以定义 $f(i,j)$ 为从 $(0,0)$ 到 $(i,j)$ 的路径数，此时递推公式是：
$$f(i,j) = f(i-1,j)+f(i,j-1)$$
逻辑是到达 $(i,j)$ 的最后一步要么是从左边 $(i-1,j)$ 向右走过来，要么是从下边 $(i,j-1)$ 向上走过来，边界情况比如 $i=0$ 时只能从下方递推，$j=0$ 时只能从左方递推。但加上限制后，我不确定该怎么扩展DP状态了。

专家解答 #

没错，这个问题确实需要带状态追踪的多维DP（可以理解为3维DP的变种），因为单纯的二维坐标无法记录“最后连续走了几步同方向”这个关键限制信息。下面给你梳理具体的建模思路：

状态定义

我们需要把状态拆分成四个子状态，用来记录到达当前点时的连续移动情况：

• $dp[i][j][0]$：到达坐标 $(i,j)$，最后一步是向右，且连续向右走了1步
• $dp[i][j][1]$：到达坐标 $(i,j)$，最后一步是向右，且连续向右走了2步
• $dp[i][j][2]$：到达坐标 $(i,j)$，最后一步是向上，且连续向上走了1步
• $dp[i][j][3]$：到达坐标 $(i,j)$，最后一步是向上，且连续向上走了2步

递推关系

根据限制条件，我们可以推导每个状态的来源：

• 对于连续向右1步的状态 $dp[i][j][0]$：只能从之前向上走的状态（不管连续1步还是2步）转移过来，也就是从 $(i-1,j)$ 向右走一步，此时连续向右步数重置为1，公式为：
  $$dp[i][j][0] = dp[i-1][j][2] + dp[i-1][j][3]$$
• 对于连续向右2步的状态 $dp[i][j][1]$：只能从连续向右1步的状态转移过来，也就是从 $(i-1,j)$ 再向右走一步，连续步数从1变成2，公式为：
  $$dp[i][j][1] = dp[i-1][j][0]$$
• 对于连续向上1步的状态 $dp[i][j][2]$：只能从之前向右走的状态（不管连续1步还是2步）转移过来，也就是从 $(i,j-1)$ 向上走一步，连续向上步数重置为1，公式为：
  $$dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][1]$$
• 对于连续向上2步的状态 $dp[i][j][3]$：只能从连续向上1步的状态转移过来，也就是从 $(i,j-1)$ 再向上走一步，连续步数从1变成2，公式为：
  $$dp[i][j][3] = dp[i][j-1][2]$$

边界条件

需要初始化起点附近的合法状态：

• 当 $i=1,j=0$：$dp[1][0][0] = 1$（仅连续向右1步），其余为0
• 当 $i=2,j=0$：$dp[2][0][1] = 1$（仅连续向右2步），其余为0
• 当 $i=0,j=1$：$dp[0][1][2] = 1$（仅连续向上1步），其余为0
• 当 $i=0,j=2$：$dp[0][2][3] = 1$（仅连续向上2步），其余为0
• 注意：当 $i>2$ 且 $j=0$ 时，所有状态都是0（因为连续向右走3步违反限制）；同理 $j>2$ 且 $i=0$ 时所有状态也是0。

最终结果

到达目标点 $(5,6)$ 的总路径数就是四个状态的总和：
$$总路径数 = dp[5][6][0] + dp[5][6][1] + dp[5][6][2] + dp[5][6][3]$$

简单来说，这个问题的DP需要在二维坐标的基础上，额外记录“最后一步方向”和“连续走了几步同方向”这两个信息，所以可以看作是3维DP（坐标+状态标记），核心是通过状态追踪避免出现连续三次同方向的移动。

备注：内容来源于stack exchange，提问作者Ri-Li