algorithm - 小偷在洞穴里编码难题

我的朋友和我分享了这个编码难题，我被卡住了。下面是谜题：
想象一下一系列的洞穴和一个小偷，在那里洞穴被描绘成
数组索引。每天，小偷都能在其中一个洞里移动
他可以回到以前参观过的洞穴，但他必须
不允许移动和环绕。
你会得到一份洞穴清单，按时间顺序每天检查一个
命令。返回这些移动是否保证您将捕获
偷了你至少一张支票。
我想到的是：
假设caves数组是0索引的。然后，你可以定义“边界”
点作为索引1和len（洞穴）-2只要你从
边界点，线性扫描到下一个边界点，重新检查
第二天到达边界点，然后扫
回到另一个边界点，你一定能抓住
小偷。例如，如果我们的洞穴长度是5：
123321和123123都能保证小偷被抓住。
但是，我不认为这是一个详尽的模板，可能有不同的方案仍然有效。我想知道有没有人有其他想法！

最佳答案

解决这一问题的一种方法是，为窃贼定义一系列可行的位置，使其在每个步骤中都不被捕获，如下所示：

Stop clauses and boundaries:
thief[-1][i] = true (for all i in [0,NUM_CAVES))
thief[k][-1] = false (for all k)
thief[k][NUM_CAVES] = false (for all k)
Step:
thief[k][i] = check[k] != i && (thief[k-1][i-1] || thief[k-1][i+1])

直觉：
在步骤i中，小偷不能（不被抓住）在正在搜索的洞穴中（这是k部分）。
此外，如果他不可能在前一轮（即第二部分，check[k] != i）的任何相邻洞穴中，则他不能在洞穴中。
这可以用i时间内的Dynamic Programming来解决，其中thief[k-1][i-1] || thief[k-1][i+1]是洞穴的数量，O(n*m)是所提供列表的长度。
计算完表格后，答案基本上是：

NOT(thief[m][0] || thief[m][1] || ... || thief[m][n-1])

这就是说，如果小偷没有被抓住，他就不能在任何山洞里。

关于algorithm - 小偷在洞穴里编码难题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46491882/