1回答

liuyubobobo

2022-02-04

已采纳

这个问题还挺好的。

整体，你的感觉是正确的，通常情况下，记忆化搜索用的每一个“参数”，都是状态的一部分。

但是，我写的这个代码有特殊的地方。特殊在哪里？特殊在，left 的信息其实是被 visited 蕴含的。

left 表示还剩多少个节点没有访问；而 visited 则使用 bit mask 记录了访问的节点。那么 visited 没有表示的节点，就是没有被访问的。我们都能通过 visited 拿到哪些节点没有被访问，自然能求出来有多少个节点没有被访问。所以，left 完全可以通过 visited 求出来。只不过，每次通过 visited 求一遍 left 太麻烦了，所以，我在这里单独列了一个参数 left 直接使用。但是，left 并非必须。left 也不是独立的一部分。

==========

最后随便说几点：

1）其实有办法，可以不使用 left，也不在 dfs 中每次通过 visited  求一个 left，就能完成整个搜索。感兴趣试试看？

2）如果使用 dp 的写法（自底向上，而非记忆化搜索），可能能够更清楚地看到根本不需要三重循环，所以我们的状态包含两个变量就够了（每重循环是对一个变量的遍历）。但因为这个课程不是专门讲 dp，同时有课程中对图的 dfs 的铺垫，使用 dfs 更直观，所以我没有讲这个问题的 dp 代码。感兴趣可以自己试试看？

3）当然，用你说的 3 维数组，整个程序也是正确的。但其实状态的定义有冗余（所以你说得对，整个程序的性能会下降。）。这其实涉及到了一个 dp 的“初级优化”问题。如果你发现自己设计的状态无法满足性能要求，可以看一看自己设计的状态之间是否是有“耦合”的。

继续加油！：）

1

1

甲骨文_0001

谢谢老师哈:)

2022-02-04

共1条回复