模拟算法搭配记忆化的实践

原题

法 1：List（TLE）

这道题我没有想出比模拟更好的解法。模拟是简单朴素的，但是当题目的数据足够大，记忆化“记住”之前干了什么以及判断是否处在之前的状态的时候，选择不同的记忆化方法会对时间复杂度产生很大的影响。

请看这个题解：

class Solution:
    def lastVisitedCell(self, grid: list[list[str]]) -> list[int]:
        arrlist = []
        r = c = 0
        arrlist.append([0, 0])
        # 直接按照题意做
        while True:
            ret = [r, c]
            match grid[r][c]:
                case "R":
                    c += 1
                case "L":
                    c -= 1
                case "U":
                    r -= 1
                case "D":
                    r += 1
            if (
                [r, c] in arrlist # 注意这一句
                or r == len(grid)
                or c == len(grid[0])
                or r < 0
                or c < 0
            ):
                return ret
            arrlist.append([r, c])

解法没有问题，但是超时了。这是为什么？

请看 if [r, c] in arrlist or ... 中的 arrlist，这是一个列表，而 Python 在执行代码的时候会遍历列表逐个进行比较，而题目给定的数据太大，导致出现 $O(n^2)$ 的时间复杂度。

同时请注意 if [r, c] in arrlist or r == len(grid) or ...，如果下一步其实越界了，但还没访问过，那么程序会先把很长的 arrlist 扫一遍，才发现越界。更合理的顺序是先判断边界，再判断是否访问过。不过即使如此，整体的时间复杂度还是下不去。我们需要考虑一种更简单的方案。

法 2：Set + Turple

class Solution:
    def lastVisitedCell(self, grid: list[list[str]]) -> list[int]:
        arrset = set() # list 太复杂了，使用 set
        r = c = 0
        arrset.add((0,0))
        # 直接按照题意做
        while True:
            ret = [r, c]
            match grid[r][c]:
                case "R":
                    c += 1
                case "L":
                    c -= 1
                case "U":
                    r -= 1
                case "D":
                    r += 1
            if (
                (r,c) in arrset
                or r == len(grid)
                or c == len(grid[0])
                or r < 0
                or c < 0
            ):
                return ret
            arrset.add((r,c))

改成这个之后，就能成功通过了。不过我们并没有对源代码进行较大的改动，在这里为什么 Set 就能比 List 更好？为什么我们在这里使用 Turple 而不是 List？

因为 Set 是基于哈希表的实现，如果我们使用 Set 就可以让查重变成 $O(1)$ 的操作，就可以成功通过了。哈希表的前提是里面的元素是“可哈希”的，这个概念有点抽象，我们可以暂且理解为“不可变”。Turple 是不可变的，而 List 是可变的，因此我们就可以用 Turple 代替 List 完成整个操作。

法 3：原地修改

就没有一点多快好省的方法吗？有的，参考灵神的原地修改方法（Deepseek 生成代码）

class Solution:
    def lastVisitedCell(self, grid: list[list[str]]) -> list[int]:
        m, n = len(grid), len(grid[0])
        r = c = 0

        while True:
            ret = [r, c]
            ch = grid[r][c]      # 先读方向
            grid[r][c] = None    # 再原地标记已访问

            match ch:
                case "R":
                    c += 1
                case "L":
                    c -= 1
                case "U":
                    r -= 1
                case "D":
                    r += 1

            if (
                r == m
                or c == n
                or r < 0
                or c < 0
                or grid[r][c] is None   # 已访问
            ):
                return ret

不仅把时间减下去了，甚至不需要额外的空间开销，最终实现了时间复杂度 $O(rc)$ ，空间复杂度 $O(1)$ 的结果。

总结

对于这类只需要标注是否重复的模拟题，可以用原地修改的方法达到最佳的效果，也可以利用哈希表和它的变体达到时间复杂度最佳的效果。另外对于 DP 的记忆化问题，这篇文章没有阐述，读者可以自行参阅其他文章。

不建议将文章内容用于训练 LLM，以免影响语料质量。本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。