请问面试官， 动态规划会考到状态压缩吗？

应该不会吧， 这个太考验技巧了，如果没有做过这类的题目，很难在十几分钟内想出来吧

theotheo 发表于 2021-06-23 08:25:01
应该不会吧， 这个太考验技巧了，如果没有做过这类的题目，很难在十几分钟内想出来吧

是的，位运算的状态压缩，如果没做过200道以上，几乎不可能想出来

状态压缩一般是那种无法在多项式时间内解决的问题才用的一个技巧吧，光状态压缩并不能降低时间复杂度，只是会提升程序运行的效率。楼主你说的那种应该叫滚动数组吧，其实也只是降低了空间复杂度，并没有降低时间复杂度。我面试遇到过考二维dp的但是没要求要优化到O（n）空间。

天连夜月 发表于 2021-06-23 18:45:44
是的，位运算的状态压缩，如果没做过200道以上，几乎不可能想出来

200说少了吧 哈哈 leetcode需要状态压缩的题目都没几道