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

是一只小可爱呀 发表于 2021-6-23 08:05
我面linkedin时一道二维dp考到了，followup问了如何状态压缩，大概写了几行code。并不要求runnable

非常感谢！！！！

mereyct 发表于 2021-06-22 16:27:23
就是压缩空间，把O(n方)的空间复杂度 压缩到 linear space O(n)。。一般会出在follow up 面试官可能会问 你还有更优解吗？

那个不是状态压缩吧？

楼主 说的 更像是 空间压缩 不是 状态压缩
比如  二维 dp 但是 一直更新  维护 一维数组 而不是保存所有 二维的结果
这 只降低了 空间复杂度 不降低时间复杂度

这个都算不上follow up把 等于解法 不用变。就是 写循环，更新状态时候 稍微改改。
我没有做过面试官 但我感觉 你可以先写出 二维解法，然后 再自己优化成 一维的，也算是 迭代优化吧。
实际上，好多production code 太复杂 看不懂， 一般就只能看 commit log, 看它是怎么从 简单版本 被无数人 改过后 变成现在这样的，还蛮符合工作需要的。

这个不叫状态压缩,一般叫dp降维吧?状态压缩dp一般是指在小数据下利用位运算解指数复杂度的DP算法.

ManuShi 发表于 2021-6-23 10:26
这个不叫状态压缩,一般叫dp降维吧?状态压缩dp一般是指在小数据下利用位运算解指数复杂度的DP算法.

https://blog.nowcoder.net/n/fcc3 ... om=nowcoder_improve
我搜了很多网站的解说，看了一下，dp里面的状态压缩也叫状态压缩：一种降纬度的状态压缩dp，其实也就是空间复杂度降低了，dp表只需要一维了。
也有你说的这种位运算的，我学习学习。

天连夜月 发表于 2021-6-23 09:08
那个不是状态压缩吧？

我搜了很多网站的解说，看了一下，dp里面的状态压缩也叫状态压缩dp：一种降纬度的状态压缩dp，还原到代码，其实也就是空间复杂度降低了，dp表只需要一维了，而时间复杂度并没有变。
也有其他留言说的这种位运算的状态压缩方法。我还没学习到，我学习学习。

yuanyao8855 发表于 2021-6-23 09:23
楼主 说的 更像是 空间压缩 不是 状态压缩
比如  二维 dp 但是 一直更新  维护 一维数组 而不是保存所有  ...

我搜了很多网站的解说，看了一下，dp里面的状态压缩也叫状态压缩：一种降纬度的状态压缩dp，其实也就是空间复杂度降低了，dp表只需要一维了。和你第一段的表述是一样的。我也是第一次学，书上这么介绍的。

也有其他留言说的这种位运算的压缩方法，我学习学习。

ManuShi 发表于 2021-6-23 10:26
这个不叫状态压缩,一般叫dp降维吧?状态压缩dp一般是指在小数据下利用位运算解指数复杂度的DP算法.

我搜了很多网站的解说，看了一下，dp里面的状态压缩也叫状态压缩dp：一种降纬度的状态压缩dp，其实也就是空间复杂度降低了，dp表只需要一维了。
也有你说的这种位运算的压缩方法，我学习学习。

mereyct 发表于 2021-6-23 10:53
我搜了很多网站的解说，看了一下，dp里面的状态压缩也叫状态压缩dp：一种降纬度的状态压缩dp，其实也就是 ...

降维的dp未必一定是一维的数组,你可以搜索一下"滚动数组优化dp".如何降维取决于转移方程依赖于哪些过往状态,转移方程不同最终降维后数组的维数也是不同的.这个知识点我个人觉得面试不会问吧?在ACM竞赛中用dp降维进行空间优化也是有一定难度的,我觉得公司面试难度不会这么高.

mereyct 发表于 2021-06-22 19:53:48
我搜了很多网站的解说，看了一下，dp里面的状态压缩也叫状态压缩dp：一种降纬度的状态压缩dp，其实也就是空间复杂度降低了，dp表只需要一维了。
也有你说的这种位运算的压缩方法，我学习学习。

这种空间降维的我认为可以先写出多维度的，再分析写出低维度的即可，如果直接写出低维度的也太难了。bit mask 才算是状态压缩，这种和dp 搞在一起，挺难的，bit mask 思想很多easy middle题目都会涉及，例如 一个数中二进制有多少个1之类的，我觉得也算是种高频题了。