Back to Leetcode

Readme

Dynamic_Programming/2184.Number-of-Ways-to-Build-Sturdy-Brick-Wall/Readme.md

latest1.8 KB
Original Source

2184.Number-of-Ways-to-Build-Sturdy-Brick-Wall

本题的突破口在于width<=10,这暗示我们可以用一个10bit的01二进制数来表示“长度为w的线段可以如何切割为若干段”。那么如何用一串01既来表示“用了哪些长度的砖”、又可以描述“这些砖是怎么排列的”呢?方法就是着眼于那些可能是切缝的位置。

例如长度为w,就有w-1个潜在的切缝位置(编号是0到w-2),我们用1表示这确实是个两块砖之间的缝,0则表示这个位置属于一块完整的砖无法切割。特别注意,我们需要虚拟地添加上左边缘的位置(想象成第-1个切缝位置)和右边缘的位置(想象成第w-1个切缝位置)。

比如w=6,那么内部有五个切缝位置,假设是10010,表示切缝位置0、3是砖与砖的交界处。另外加上左边缘-1和右边缘5,所以总共有四个交界位置:-1,0,3,5,这说明有三块长度分别是1、3、2的砖拼接起来。也就是说,任意两个1之间的index之差,表示了中间有多少块砖。

考虑到w很小,我们穷举所有对w的切割方案,看看切割出来的每一小段是否存在于bricks里面。都存在的话就是一个合法的切割(拼接)方案。

我们得到所有合法的切割方案之后(用bitmask的形式表示),就是常规的状态压缩DP。我们用dp[i][state]表示第i层用state这种拼接方式的话可以有多少种方案。显然dp[i][state]+=dp[i-1][state1]其中state1和state不能在同一个切缝位置上都是拼接点,也就是说必须满足(state & state1) == 0。这个思想和paint house非常相似,在那道题里,任何相邻的房子不能是同一种颜色。

最终答案是 sum{dp[height-1][state]} for all states