在那个过河卒逃过了马的控制以超级超级多的走法走到了终点之后,这匹马表示它不开心了…… 于是,终于有一天,它也过河了! 由于过河马积累了许多的怨念,所以这次它过了河之后,再也没有什么东西可以限制它,它可以自由自在的在棋盘上驰骋。一开始,它是在一个n行m列棋盘的左下角(1,1)的位置,它想要走到终点右上角(n,m)的位置。而众所周知,马是要走日子格的。可是这匹马在积累了这么多怨念之后,它再也不想走回头路——也就是说,它只会朝向上的方向跳,不会朝向下的方向跳。 那么,这匹马它也想知道,它想从起点跳到终点,一共有多少种走法呢?算法描述
时间: 2023-03-21 11:02:25 浏览: 320
这是一道典型的动态规划问题。定义一个二维数组dp,其中dp[i][j]表示马从起点(1,1)跳到(i,j)位置的不回头路走法总数。对于每个位置(i,j),它可以由(i-2,j+1)或者(i-1,j+2)两个位置跳过来,因此有状态转移方程:dp[i][j] = dp[i-2][j+1] + dp[i-1][j+2]。
边界条件:dp[1][1] = 1,dp[i][j] = 0(当(i,j)位置超出棋盘范围或者是向下跳)。
最终,dp[n][m]就是马从起点跳到终点的不回头路走法总数。
代码示例(Python):
```python
def horseJump(n, m):
dp = [[0] * (m+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
if i >= 2 and j <= m-1:
dp[i][j] = dp[i-2][j+1] + dp[i-1][j+2]
return dp[n][m]
n, m = 8, 8
res = horseJump(n, m)
print(res)
```
阅读全文