Code:
https://tinyurl.com/yy3a5na4
问题描述:
一维座标，每次可以往右走a格，或者往左走b格，请问走到 x 最少需要几步。
限制:
可以连续往右走无限次a
不能连续往左走两次b
不能走到地雷座标，如果一定会碰到地雷或是走不到x，回传-1。
解答:
1.BFS穷举各种走法，一步一步慢慢穷举。
2.接着记忆化走过的点。
visited[10][0] 代表10这个点用往前走的方式走过了
visited[10][1] 代表10这个点用往后走的方式走过了
问题:
为什么记忆化搜寻的visited要二维的，不是只要一维就好了吗?
我想说直接visited[10] = true/false，但结果这样会过不了测资= =
我觉得有走过的点不管是来回走过都是一样的意义呀代表你这个点的所有可能都走过了
何必再分来回的记忆化呢?在Discuss上等不到解释，故上来发文感恩

因为不能连续走两次 b?

我想你应该搞错了第二维的意思, 那个是“你用哪步来这里”也就是它不是在记下一步而是前一步因为问题在于你的前一步是 b 时下一步不能是 b你如果没记着是怎么来的话下一步会不知道该不该有 b

一个用来记录 上一步非b最少步数 一个是上一步为b最少步数 dp式推一下就会知道这样分不能省

我回家拿那个测资失败的例子推同额推看好了感谢我还是没感觉感谢大大

想到一个反例了: 往右走 2, 往左走 1, 则你走不到起点以左这在你把两种状态混在一起时是无法得出来的结论修正: 走不到起点左一格以左如果限向右座标的话也有反例: 往右 5 往左 2, 则走不到 1

所以我们不能抹杀掉8走到6的可能感谢