google上门跪经

14417335 发表于 2019-2-12 07:51
难题。
一点greedy的地方是：每次要么去救公主，要么去加血。这样目的性就减为加血点和公主点。
另外我感 ...

好像有道理，我当场肯定想不出这样的思路，具体代码怎么架构当场写出来就更不会了。

dertas1993 发表于 2019-2-12 07:54
这题真的能简单的backtrack么，考虑到可以设计一个需要回头吃血的极限情况的话，backtrack大概并不好用吧？ ...

path应该可以穷尽吧，正格子吃完一次就归0了，下次再走到就不加血了，所以不可能无限走下去吧

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

14417335 发表于 2019-2-12 07:51
难题。
一点greedy的地方是：每次要么去救公主，要么去加血。这样目的性就减为加血点和公主点。
另外我感 ...

感觉还要一个东西才能保证dfs结果是最短path吧

LZ哪里面的？

wtcupup 发表于 2019-2-12 08:06
LZ哪里面的？

我在NYC面的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

哎不管怎么说安慰楼主还是要，这个题真的是难的一匹。。。我上我反正直接gg了

1and10 发表于 2019-2-12 07:47
那就是把所有path都穷举一遍么，用当前最少血量来做backtracking的early termination?

嗯。我能想到就是这么做了。就是时间复杂度很高了。exponential的。

14417335 发表于 2019-2-12 07:51
难题。
一点greedy的地方是：每次要么去救公主，要么去加血。这样目的性就减为加血点和公主点。
另外我感 ...

不能绕着走吗，那样就没法greedy了，绕着扣血少或者不扣血的地方走