two Sigma新鲜挂经

请问下楼主的面试流程？这是OA后面一轮还是final round啊？

楼上所有说最短路的全是错的。
bellman ford可以检测负环， 但是不能在有负环的图里找到无环最短路。
事实上可以证明这个问题是np hard的，它比hamilton path问题严格地更难， 题目数据范围n<=18也暗示了这道题并不需要多项式时间算法。
不难发现一个类似于hamilton路dp解的算法复杂度是2^n * n^2, 在这个数据范围刚好够用。

同意楼上的说法，n<=18的情况下，其实可以用状态压缩dp去做这道题,dp[state][pos]，state用二进制表示每种货币是否使用过，最后从所有合法终态里选取最大值就是答案了。