【动态规划】【状态压缩】LCP04 覆盖-阿里云开发者社区

作者推荐

【广度优先搜索】【网格】【割点】【推荐】1263. 推箱子

本文涉及知识点

动态规划汇总

LCP04 覆盖

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。

输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。

输出：一个整数，代表最多能在棋盘上放的骨牌数。

示例 1：

输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]

输出：2

解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）

示例 2：

输入：n = 3, m = 3, broken = []

输出：4

解释：下图是其中一种可行的摆放方式

限制：

1 <= n <= 8

1 <= m <= 8

0 <= b <= n * m

动态规划

动态规划状态数

mask &(1 << j) 表示第j列空闲，没有放置骨牌，也没有损坏。其它位置不限：损坏、骨牌、空闲皆可。

pre[mask] 表示第i行开始处理时，上一行状态为mask的最多骨牌数。

dp1[mask] 表示处理完第i行的竖放后，最多骨牌数。

dp2[mask] 表示处理完第i行的竖放横放后，最多骨牌数。

动态规划的转移方程

mask1 是上一行的状态。

mask2 = mask ^ 当前行坏掉的位置。

mask3 = mask1 & mask2

枚举所有 mask4(竖放），mask4是mask所有非0子序列。每个mask1都要枚举mask4

mask5是竖放完的状态 mask2 ^ mask4。

枚举mask5的所有子序列mask6，横放的状态，合法状态：数量必须是偶数，两两挨在一起。

时间复杂度: O(m3ⁿ)

动态规划的初始状态

pre[0]=0，其它-100。

动态规划的填表顺序

按行处理。

动态规划的返回值

pre的最大值。

代码

核心代码

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class CBitCounts
{
public:
  CBitCounts(int iMaskCount)
  {
    for (int i = 0; i < iMaskCount; i++)
    {
      m_vCnt.emplace_back(bitcount(i));
    }
  }
  template<class T>
  int bitcount(T x) {
    int countx = 0;
    while (x) {
      countx++;
      x &= (x - 1);
    }
    return countx;
  }
  vector<int> m_vCnt;
};
class CEnumMask2
{
public:
  CEnumMask2(int iMaskCount):m_iMaskCount(iMaskCount)
  {
  }
  template<class GetMask2,class On>
  void Enum(GetMask2 getMask2,On on )
  {
    for (int mask1 = 0; mask1 < m_iMaskCount; mask1++)
    {
      const int mask2 = getMask2(mask1);
      for (int mask3 = mask2; mask3; mask3 = mask2 & (mask3 - 1))
      {
        on(mask1, mask2, mask3);
      }
    }
  }
  const int m_iMaskCount;
};
class Solution {
public:
  int domino(int n, int m, vector<vector<int>>& broken) {
    const int iMaskCount = 1 << m;
    vector<int> vCan(n, iMaskCount-1);
    for (const auto& v : broken)
    {
      vCan[v[0]] ^= (1 << v[1]);
    }   
    CBitCounts bitCnt(iMaskCount);
    vector<int> vVilidH(iMaskCount,-100);
    vVilidH[0] = 0;
    for (int i = 1; i < iMaskCount; i++)
    {
      int end = i & (-i);
      int end1 = end * 2;
      if (i & end1)
      {
        vVilidH[i] = 1 + vVilidH[i ^ end ^ end1];
      }
    }
    vector<int> pre(iMaskCount, -100);
    pre[0] = 0;
    CEnumMask2 enumMask(iMaskCount);
    for (int r = 0; r < n; r++)
    {
      vector<int> dp1(iMaskCount, -100);
      dp1[vCan[r]] = *std::max_element(pre.begin(), pre.end());//不竖放
      enumMask.Enum([&](int mask1) {return vCan[r] & mask1; }, [&](int mask1, int mask2, int mask3)
        {MaxSelf(&dp1[vCan[r] ^ mask3], pre[mask1] + bitCnt.m_vCnt[mask3]); });
      vector<int> dp2 = dp1 ;//不横放
      enumMask.Enum([](int mask1) {return mask1; }, [&](int mask1, int mask2, int mask3)
        {if (vVilidH[mask3] <= 0)
      {
        return;
      }
      MaxSelf(&dp2[mask1 ^ mask3], dp1[mask1] + vVilidH[mask3]); });
      pre.swap(dp2);
    }
    return *std::max_element(pre.begin(), pre.end());
  }
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  int m,n;
  vector<vector<int>> broken;
  {
    Solution sln;
    n = 2, m = 3, broken = { {0, 0},{0, 1} };
    auto res = sln.domino(n, m, broken);
    Assert(2, res);
  }
  {
    Solution sln;
    n = 2, m = 3, broken = { {1, 0},{1, 1} };
    auto res = sln.domino(n, m, broken);
    Assert(2, res);
  }
  {
    Solution sln;
    n = 3, m = 3, broken = {  };
    auto res = sln.domino(n, m, broken);
    Assert(4, res);
  }
  {
    Solution sln;
    n = 4, m = 3, broken = { {1,0},{1,1} };
    auto res = sln.domino(n, m, broken);
    Assert(5, res);
  }
  {
    Solution sln;
    n = 3, m = 4, broken = { {2,2},{2,3} };
    auto res = sln.domino(n, m, broken);
    Assert(5, res);
  }
}

优化

枚举所有合法状态，再枚举竖放状态。不用枚举前一行的状态。竖放的状态就是前一行状态。

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class CBitCounts
{
public:
  CBitCounts(int iMaskCount)
  {
    for (int i = 0; i < iMaskCount; i++)
    {
      m_vCnt.emplace_back(bitcount(i));
    }
  }
  template<class T>
  int bitcount(T x) {
    int countx = 0;
    while (x) {
      countx++;
      x &= (x - 1);
    }
    return countx;
  }
  vector<int> m_vCnt;
};
class Solution {
public:
  int domino(int n, int m, vector<vector<int>>& broken) {
    const int iMaskCount = 1 << m;
    vector<int> vCan(n, iMaskCount-1);
    for (const auto& v : broken)
    {
      vCan[v[0]] ^= (1 << v[1]);
    }   
    CBitCounts bitCnt(iMaskCount);
    vector<int> vHMax(iMaskCount);  
    for (int i = 1; i < iMaskCount; i++)
    {
      int end = i & (-i);
      int end1 = end * 2;
      vHMax[i] = (i & end1) ? (1 + vHMax[i ^ end ^ end1]) : (vHMax[i ^ end]);
    }
    vector<int> pre(iMaskCount, -100);
    pre[0] = 0;
    for (int r = 0; r < n; r++)
    {
      vector<int> dp(iMaskCount, -100);
      dp[vCan[r]] = pre[0];
      for (int mask = vCan[r]; mask; mask = (mask - 1) & vCan[r])
      {//当前行放置阵了骨牌的位置
        for (int maskH = mask; ; maskH = (maskH - 1) & mask)
        {
          MaxSelf(&dp[vCan[r] ^ mask], vHMax[mask ^ maskH] + bitCnt.m_vCnt[maskH] + pre[maskH]);
          if (0 == maskH)
          {
            break;
          }
        }
      } 
      pre.swap(dp);
    }
    return *std::max_element(pre.begin(), pre.end());
  }
};

2023年2月版

//通过 x &= (x-1)实现

int bitcount(unsigned x) {

int countx = 0;

while (x) {

countx++;

x &= (x - 1);

}

return countx;

}

class Solution {

public:

int domino(int R, int C, vector<vector>& broken) {

m_iMaskNum = 1 << C ;

vector vRowMask(R, m_iMaskNum - 1);

for (const auto& v : broken)

{

vRowMask[v[0]] &= ~(1 << v[1]);

}

vector pre(m_iMaskNum, -1);

pre[0] = 0;

for (int r = 0; r < R; r++)

{

vector dp(m_iMaskNum, -1);

for (int pr = 0; pr < m_iMaskNum; pr++)

{

const int& iPreNum = pre[pr];

if (-1 == iPreNum)

{

continue;

}

const int iCurRMask = vRowMask[r];

const int iMaxVMask = iCurRMask & pr;

//vMask枚举所有的竖放

for (int vMask = iMaxVMask;; vMask = iMaxVMask & (vMask - 1))

{

const int iMaxHMask = iCurRMask &(~vMask);

for (int hMask = iMaxHMask;; hMask = iMaxHMask& (hMask - 1))

{

const int iHNum = GetHNum(hMask);

if (iHNum < 0)

{

continue;

}

dp[iMaxHMask & ~hMask] = max(dp[iMaxHMask & ~hMask], iPreNum + iHNum + bitcount(vMask));

if (0 == hMask)

{

break;

}

if (0 == vMask)

{

break;

}

pre.swap(dp);

}

return *std::max_element(pre.begin(), pre.end());

}

int GetHNum(int iMask)

{

int iNum = 0;

while (iMask)

{

int iEndMask = (iMask&(-iMask));

int iPreMask = iEndMask << 1;

if (!(iMask & iPreMask))

{

return -1;

}

iMask -= iEndMask;

iMask -= iPreMask;

iNum++;

}

return iNum;

}

int m_iMaskNum;

};

【动态规划】【状态压缩】LCP04 覆盖