力扣上的一题..
来源：11-1 结语
慕桂英雄
2019-10-18
https://leetcode-cn.com/problems/broken-board-dominoes/
季赛比赛，当时没做出来，后来看题解，dfs的思路可以实现。
题解里dp的思路就没怎么理解了。。
为啥k0的取值要和上面的所有红色有关联？不应该只和k1、k5有关吗？
不太理解题解代码里dp[i]里面的语义，似乎使用了滚动数组。
https://leetcode-cn.com/problems/broken-board-dominoes/solution/dong-tai-gui-hua-hua-dong-chuang-kou-by-ga-beng-cu/
写回答
1回答
-
状态压缩 dp。dp[i]里的表示状态，看做是一个二进制数，0代表对应位没有被覆盖；1代表被覆盖。一个数字 i 可以表示之前的五个位置的覆盖情况。
具体要想解释清楚，很复杂了，在问答区不是一句话两句话可以解释清楚的。专门做视频要用一章的内容讨论。这也超出这个课程的范畴了。我的图论课程在讲解哈密尔顿回路问题时，涉及了状态压缩的问题，有兴趣可以参考：https://coding.imooc.com/class/370.html
状态压缩 dp 在任何面试中都不可能考到。放心。有机会我专门讲动态按规划的话，肯定会介绍相关内容的，但只是作为提高用。如果感兴趣，可以在互联网上搜索“状态压缩 dp”进行自学。
加油！：）
012019-10-29
相似问题