这道题不是动态规划吗
by allen2010 @ 2023-10-11 19:29:44
@[ERIC_XIE](/user/389915)
by allen2010 @ 2023-10-11 19:30:32
请使用状态储存和转移的方式处理该问题，可以使用记忆化搜索或者动态规划。
```Python
from functools import [cache](/user/83130)
@[cache](/user/83130)
def operate(n, m):
if n < 0 or m < 0 or (n, m) in banned_position or (n, m) == (position[0], position[1]):
return 0
elif (n, m) == (0, 0):
return 1
else:
return operate(n-1, m) + operate(n, m - 1)
n, m, *position = map(int, input().split())
banned_position = [(position[0] - 1, position[1] - 2),
(position[0] - 2, position[1] - 1),
(position[0] + 1, position[1] + 2),
(position[0] + 2, position[1] + 1),
(position[0] - 1, position[1] + 2),
(position[0] + 1, position[1] - 2),
(position[0] - 2, position[1] + 1),
(position[0] + 2, position[1] - 1)]
print(operate(n, m))
```
↑，模块自带修饰符实现记忆化搜索。
by Terrible @ 2023-10-11 19:32:02
（秀才表情.gif）
洛谷特有的 User $@$ 补全。
你看看这个 https://blog.csdn.net/Tisfy/article/details/129164772 学习一下 cache 修饰符。
或者学一下动态规划和手动记忆化，https://blog.csdn.net/weixin_41695199/article/details/103840855。
by Terrible @ 2023-10-11 19:35:44
```python
from functools import cache
＠cache
def operate(n, m):
if n < 0 or m < 0 or (n, m) in banned_position or (n, m) == (position[0], position[1]):
return 0
elif (n, m) == (0, 0):
return 1
else:
return operate(n-1, m) + operate(n, m - 1)
n, m, *position = map(int, input().split())
banned_position = [(position[0] - 1, position[1] - 2),
(position[0] - 2, position[1] - 1),
(position[0] + 1, position[1] + 2),
(position[0] + 2, position[1] + 1),
(position[0] - 1, position[1] + 2),
(position[0] + 1, position[1] - 2),
(position[0] - 2, position[1] + 1),
(position[0] + 2, position[1] - 1)]
print(operate(n, m))
```
by Terrible @ 2023-10-11 19:36:53
感谢各位大佬！
by ERIC_XIE @ 2023-10-11 20:14:09