遇到一道机器人走方格的变种

给一个n*m的grid，机器人从左上角到右下角，可以上下左右四个方向移动，但是不能走重复的房间， 算有多少中走法。
有没有同学有思路的？dp估计行不通，难道要dfs到底？

求会的同学解答

这个问题在组合数学领域中有很多研究，叫做 Self-Avoiding Walk，应该是#P-complete（NP-hard以上）的问题

在grid维度为n * 2时有解析解，维度为n * 3时有递推表达式：
http://mathworld.wolfram.com/Self-AvoidingWalk.html

如果不想做naive dfs，有一些优化的counting方法（还是指数复杂度）+并行化，好像涉及到一些编码方式还有剪枝什么的，参考这篇（以及相关引用的文章）：
Enumeration of self-avoiding walks on the square lattice
https://arxiv.org/pdf/cond-mat/0404728.pdf

维基百科：
https://en.wikipedia.org/wiki/Self-avoiding_walk

感觉dfs + memorization:
- 每走到一个点先查有没有之前memorization
- 每从一个点走完返回前 记录下从当前点到终点路径数量

老哥， 有想法吗？dfs + memorization 是不可以的，