🐶虚拟上门

aug828 发表于 2021-4-21 12:41
第四题给的数据规模很小，是不是就是dfs暴力就可以了？

我写的dfs 然后followup那里的话复杂度爆炸了

PocketOffer 发表于 2021-4-21 13:13
嗨，楼主，最后一题有步数限制嘛？如果没步数限制的话岂不是可以有无数种可能了吗？把所有非障碍点走一遍
...

就是每个点走过且只走一遍，步数是定死的

jil261 发表于 2021-4-22 01:14
就是每个点走过且只走一遍，步数是定死的

这个题，要求总共多少种走法，听起来像是动规了。
但是，走的方向是四个方向。没有明显看起来可以递归求解的地方，不知道从哪里下手

请问楼主，第二题followup应该怎么搞

tough2016 发表于 2021-4-22 05:20
请问楼主，第二题followup应该怎么搞

不会啊，太难了

aug828 发表于 2021-4-22 04:45
这个题，要求总共多少种走法，听起来像是动规了。
但是，走的方向是四个方向。没有明显看起来可以递归求 ...

不太会。。

jil261 发表于 2021-4-22 05:28
不会啊，太难了

segment tree可以handle mutable inputs

jil261 发表于 2021-4-22 01:10
就是C++里面要free 一颗二叉树，不让用递归

morris post order traversal

请问 LZ 第二题能具体说一下嘛？连续 k 项乘积就是类似阶乘？

jil261 发表于 2021-4-22 01:14
就是每个点走过且只走一遍，步数是定死的

能想到只有backtrack，太brutal force了，如果有toplogical order的话应该可以用dp