网易2018春招笔试
前不久被网易的笔试虐了2次,因此特地做一个记录:
给出2个数a, b(b必定是偶数), 把a变成b,其中有3种操作:
+2, 需要对应的cost,
-2, 需要对应的cost
*2, 需要对应的cost,
求a变成b需要的最少cost
当时脑子一热,就用bfs, 用一个结构体保存状态,后来发现爆内存了。
那就改用dfs, 但是没有往剪枝这个方向去想,总是认为应该是用动态规划才有适合的解法——这也是我对最优化问题的懵逼之处。
后来,第二次笔试,再看到一题,发现也许真的是dfs + 剪枝的技巧呢?
刚开始,也是没有想太多,直接dfs,暴力搜,发现爆内存。
没理由啊?——难道一定要用动态规划,但是四维表示状态,100四次方 = 1亿——不合理呀?
后来问一下同学才发现一点剪枝的技巧就是:
一旦发动攻击了就一直攻击了,否则必定不是最优解。
每次搜索,可以估算剩余回合数。
社会社会,是我太菜了- - 。。。
dfs的剪枝优化大法。。。