刷leetcode的一点困惑：最优解还是最擅长的解？

各位地里的大佬好，我统计本硕毕业，最近为了找ds，mle相关工作，也加入了leetcode大军，现已刷题300+，对基本的数据结构和算法也有一个大致的了解，基本上easy，medium都能刷，取决于题目的类型之前是否遇过。最近在刷题的过程，看到典型的dp问题，会不由自主的先用暴力法穷举一遍，然后用备忘录来优化时间复杂度，不过有些题虽然能跑过大多数test case 46/49, 却不能一次ace，但bottom up法却不是特别熟练，很难在1 hour interview用清晰的思路完整的给面试官讲解每一步的思路。

请教地里的各位大大，对于这种类型的问题，（不限于dp），是强行记住最优解，还是采用自己比较熟悉的数据结构还是算法来把解法层层剖析，以及如何优化时间，空间复杂度，（虽然不一定能过所有test case），希望指点迷津。

尝试把最优解变成最擅长解…
因为面试很加分的
1小时面试， LIS 你是喜欢上来就给nlogn 解的
还是 先给你n^2 然后说 “我知道nlogn的但是没时间写了”

我觉得要感受一下一道题给你带来了什么，如果是“学到了新算法思路”或者是“帮助你注意到了小的细节处理方法/语法”，那还是有收获的；如果感觉只是提高了比如DFS的熟练度，那收益其实很小，进入舒适区了。面试他有的人就喜欢你把什么方法都想明白，我觉得还是要一题多解拓展思路，帮助思维灵活起来。比起做不出来，那种面试官引导你往最优解走，却因为思路受限等因素想不出最优解，这个对面试结果更伤。

@ND0406, 多谢提点，明白了，看来还是得把很多问题的最优解再好好研究一番，内化为自己的。

both        

我觉得解知道的越多越好，不一定bug free，但是要让面试官知道你知道各种解有各种复杂度，至少能用几个伪代码函数描述清楚。然后就硬着头皮写面试官要你写的那个，不是bug free也比只会一个解强。

其实我面狗的时候，碰到了个dp，先用dfs穷举search space，然后分析dfs tree哪些枝可以被记录，然后最后告诉面试官根据这个dfs tree推出来的状态转移方程能写成bottom up，面试官还是很享受这种表演的。其实这种题做多了经典的很快就能写出bottom up，hard难度的写个dfs + memo应该没所谓毕竟情况可能多和复杂，dfs比较直观

Dexuan 发表于 2021-01-05 12:46:13
其实我面狗的时候，碰到了个dp，先用dfs穷举search space，然后分析dfs tree哪些枝可以被记录，然后最后告诉面试官根据这个dfs tree推出来的状态转移方程能写成bottom up

狗家面试的特点 地理都有 面试真的是把答案一步步喂到你嘴里 面试很舒服 结果往往很残忍