求两道google onsite题目的详细解答~跪谢！！

bambloo 发表于 2018-4-7 08:31
你的问题就是用了无向图，用hashmap可以建有向图（其实二维数组也可以，不过需要输入都是数字），代码有 ...

有向图还是有环啊： 举个例子， a->b, c; b ->c
这个就是有向图，还是有环还是解不出来。。。。。

sth830 发表于 2018-4-7 08:38
有向图还是有环啊： 举个例子， a->b, c; b ->c
这个就是有向图，还是有环还是解不出来。。。。。

这就不是环了哥

补充内容 (2018-4-7 09:13):
source是a，sink是c，不是环

bambloo 发表于 2018-4-7 09:12
这就不是环了哥

这是环，解不出来，用dp的话，有环，没法做，你能不能讲一下详细的思路，伪代码也行。。。

应该没有多项式做法。还是考虑如何高效地dfs吧....

rsents 发表于 2018-4-7 10:48
应该没有多项式做法。还是考虑如何高效地dfs吧....

啊我刚刚回复的是第一题 忘记说了....

第一题是 Maximum Independent Set Problem， 本身是NP问题，这道题目还加了权重， 只能尝试优化dfs..

第一题难道不是蠡口的house robber III吗

flyPacific111 发表于 2018-4-8 12:53
第一题难道不是蠡口的house robber III吗

单是这个不是树，而是可能有环的图，所以那个解法有点问题，我试过了

hjh1011 发表于 2018-4-7 05:19
前两天写的扫地机器人，求大神斧正

跪谢！！！

第一题哪位大神能分享一下解