面试不用动态规划用记忆化递归可不可以？

有些题目用动态规划感觉不太好想。如果写记忆化递归不用动态规划面试的时候面试官会不会觉得写的不好？复杂度应该都是一样的。

小猪羔子 发表于 2021-4-27 13:00
不建议直接用dfs+cache吗？

写不出来时总是先写dfs + cache简单吧。然后再想办法bottom-up dp避免calls

怎么可能一样，虽然方向相反，能做出来可以，但是时间复杂度不行，有call stack

top-down dp = dfs + cache

可以用top-down dp

lllxin37 发表于 2021-4-27 12:28
top-down dp = dfs + cache

可以用top-down dp

不建议直接用dfs+cache吗？

说真的，这个看面试官水平，有些很菜的面试官只懂一种做法，然后明明他菜，结果你挂