面试如果被问到DP的题目

敢不敢上来就给最优化的解法？

还是需要按部就班：
第一步： Intuitively， use recursive
第二步： 优化recursive  with Top down DP
第三步： 优化Top down with bottom up DP
第四步： More tricks for final optimization

感觉4部的戏会比较足   上来就给最优解    后面剩的时间演什么？

最好简单说一下brute force然后之间说dp解。感觉四步曲写不完implementation？

MachaIceCream 发表于 2020-10-22 03:31
最好简单说一下brute force然后之间说dp解。感觉四步曲写不完implementation？

四个都写肯定写不完   需要有侧重

最后一步最优解肯定要写 （如果能写出来）

第一步如果简单也写一下   中间挑一个写写？  其他略过

这样安排怎么样  

1. 第一步可以省略，除非不能一下子看出可以用 dp 解。
2. top down 还是 bottom up 无所谓，给出状态转移方程就行。
3. 并不一定要写完再优化空间，可以先分析 dp 矩阵和运行方式，怎么优化写的时候心里自然就有数了，简单的题这个其实挺一目了然的。
4. 复杂一点的 dp 题面试的时候可能没时间优化，建议 2 和 3 要先做，这样就算写完没时间改也可以简单叙述一下让面试官清楚思路，比如股票四那道题。

myonlysunshine 发表于 2020-10-21 13:02:08
四个都写肯定写不完   需要有侧重

最后一步最优解肯定要写 （如果能写出来）

第一步讲思路 之后直接讲二/三的解法。个人觉得四可能没空 让面试官follow up就好。求米求米。