Water and Jug Problem面试的时候给哪个答案好# JobHunting - 待字闺中
e*s
1 楼
LC 365 Water and Jug Problem
最优解是用最大公约数
1. 如果用最优解, 即使知道答案这种解, 全部证明依然写3页, 之前没有遇到过几乎不
可能面试的时候现场想出来的. (想到最大公约数容易, 但是要证明互质容量的桶一定
能reach到范围[0,sum]内所有的答案, 不容易, 第一次做的时候想到了这个猜想, 但是
没有信心证明下去)
2. 用DP
3. 直接和面试官说我以前见过这个题, 这个题的最有解是balabala
那种方法最好?
最优解是用最大公约数
1. 如果用最优解, 即使知道答案这种解, 全部证明依然写3页, 之前没有遇到过几乎不
可能面试的时候现场想出来的. (想到最大公约数容易, 但是要证明互质容量的桶一定
能reach到范围[0,sum]内所有的答案, 不容易, 第一次做的时候想到了这个猜想, 但是
没有信心证明下去)
2. 用DP
3. 直接和面试官说我以前见过这个题, 这个题的最有解是balabala
那种方法最好?
