[编程题]小军砌墙 难得离谱 讲的明白 位运算+动态规划

这套题真的难的离谱，2小时做完的都是些什么神仙？

截止5月11日，还没有题解，就让我来抛砖引玉吧。

首先咱们最容易想到的是类似dfs那种递归算法，这个我也贴在后面了，但是超时了。

我重点来讲解下面的 位运算+动态规划 算法。

首先我们来考虑铺一行的可能性，我们定义一个函数f(pos int)来从pos位置开始铺砖，那么：
1.我们可以铺一块2格的红砖，然后调用f(pos+2)
2.我们可以铺一块3格的绿砖，然后调用f(pos+3)

然后在递归搜索的过程中用什么记录状态呢，可以用bool值数组来记录，为1表示一块转结束的位置。
例如 w=9 时可以得到下列状态码：
S1:010101001
S2:010100101
S3:010010101
S4:001010101
S5:001001001

要存储这样的状态码可能最容易想到的是bool数组，但是注意到题干里限制了 2 <= W <= 30，因此咱们可以大胆一点，可以使用int32来作为32位bool来用，省空间是小事，主要是后面我们需要对比两行的间隙，相比与遍历两个bool数组，直接对两个int32进行 位与 效率就高多了。

好了，咱们现在有了铺满9格的5种可行的状态码，那么只有一行的时候每种状态码都只可能出现1次，咱们可以建立一个数组dp[5]来记录每种状态码可能出现的次数，其中每个元素均为1。

那多行呢？题干要求相邻的两行不能出现任何上下对齐的砖缝。
那怎么判断缝隙对没对齐呢？很简单，位与一下。
比如我们当时按S1铺第1行，按S3铺第2行是否符合要求？
只需要将两个状态码 位与，得S:010000001，除了末尾，中间有一处对齐了，因此非法。
如果两个状态码 位与 得S:000000001，则中间没有对齐的缝隙，这个组合是合法的。

进一步，我们可以根据上一行的可能性数组和状态转移来计算。
例如，容易判断S2,S3->S5可行，那么这一行按照S5来铺的可能性等于上一行按S2，S3来铺的可能性之和，实际上就是运用动态规划的思想。

下面是Golang代码，没有什么高级语法，就算你学的Java/Python等应该也都能读懂。

如果这篇解答对你有帮助，不妨点个赞吧！

//位运算+动态规划
package main

import "fmt"

var w,h int

//可行的间隙码
var gaps []int

//铺一行
func f(pos int,gap int){
    if pos>w{            //越界
        return
    }else if pos==w{    //已铺完
        gaps=append(gaps, gap)
    }else{                //未铺完
        f(pos+2,gap<<2+1)
        f(pos+3,gap<<3+1)
    }
}

func main() {
    fmt.Scan(&w,&h)

    //不多于三行只有一种可能性
    if w<=3{
        fmt.Println(1)
        return
    }

    //开始搜索可行状态码
    f(0,0)

    //输出可行的间隙码
    //for _,v:=range gaps{
    //    fmt.Printf("S%d:%09b\n",i+1,v )
    //}

    //dp[i]表示当前行按照S[i]来铺的可能性
    dp:=make([]int, len(gaps))

    //初始化，单行的时候每一种状态均为1
    for i:=0;i< len(dp);i++{
        dp[i]++
    }

    //动态规划
    for i:=1;i<h;i++{
        tmp:=make([]int, len(gaps))
        for j:=0;j< len(dp);j++{
            for k:=0;k< len(dp);k++{
                if gaps[j]&gaps[k]==1 {
                    tmp[k]+=dp[j]
                }
            }
        }
        dp=tmp
    }

    //可能性求和
    ans:=0
    for _,v:=range dp{
        ans+=v
    }
    fmt.Println(ans)
}

//暴力搜索
package main

import "fmt"

var w,h int

type list []int

func (l list)has(i int) bool {
    for _,v:=range l{
        if v==i{
            return true
        }
    }
    return false
}

func f(line,pos int,preGaps,curGaps []int) int {
    if list(preGaps).has(pos) || pos>=w-1 || line>=h {
        return 0
    }else {
        ans:=0
        curGaps= append(curGaps, pos)
        if pos<w-3{
            ans+= f(line,pos+2,preGaps,curGaps)
            ans+= f(line,pos+3,preGaps,curGaps)
            return ans
        }else{
            if line==h-1{
                ans++
            }else{
                ans+= f(line+1,2,curGaps,make([]int,0))
                ans+= f(line+1,3,curGaps,make([]int,0))
            }
        }
        curGaps=curGaps[:len(curGaps)-1]
        return ans
    }
}

func main() {
    fmt.Scan(&w,&h)
    if w<=3{
        fmt.Println(1)
        return
    }
    ans:=0
    ans+=f(0,2,make([]int,0),make([]int,0))
    ans+=f(0,3,make([]int,0),make([]int,0))
    fmt.Println(ans)
}

• dfs1用于求每一层总共的砌砖方法。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w, h;
vector<int> state;
long long dp[15][2000];
void dfs1(int i, int now, vector<int>& state){
	if(((1<<w)&now)!=0){state.push_back(now); return; }
	vector<int> a = { 2, 3 };
	for (auto &x :a){
		if (i + x>w) continue;
		int mask = 1 << (i + x);
		dfs1(i + x, now | mask, state);
	}
}
int main(){
	cin >> w >> h;
	for (int i = 0; i < 15; i++)
	for (int j = 0; j < 2000; j++)
		dp[i][j] = 1;
	dfs1(0, 0, state);
	int n = state.size();
	long long res = 0;
	for (int i = 1; i<h; i++)
	for (int j = 0; j < n; j++)
	{
		dp[i][j] = 0;
		for (int k = 0; k < n; k++){
			if ((state[k] & state[j]) != (1 << w)) continue;
			dp[i][j] += dp[i - 1][k];
		}
	}
	for (int i = 0; i < n; ++i) res += dp[h - 1][i];
	cout << res;
	return 0;
}

w,h=map(int,input().split())
state=[]
def dfs1(i,now):
    if 1<<w & now !=0:
        state.append(now)
        return
    for x in [2,3]:
        if i+x>w: continue
        mask=1<<(i+x)
        dfs1(i+x,now|mask)
dfs1(0,0)
dp=[[1]*len(state) for _ in range(h)]
for i in range(1,h):
    for j in range(len(state)):
        dp[i][j]=0
        for k in range(len(state)):
            if state[k]&state[j]!=1<<w:continue
            dp[i][j]+=dp[i-1][k]
res=0
for i in range(len(state)): res+=dp[h-1][i]
print(res)

#include <bits/stdc++.h>
using namespace std;

int r = 2, g = 3;

void dfs(int cur, int w, int curstate, vector<int> &valid_states)
{
    if (cur == w)
    {
        curstate ^= 1 << (w - 1);
        valid_states.push_back(curstate);
        return;
    }
    if (cur + r <= w)
    {
        dfs(cur + r, w, curstate | (1 << (cur + r - 1)), valid_states);
    }
    if (cur + g <= w)
    {
        dfs(cur + g, w, curstate | (1 << (cur + g - 1)), valid_states);
    }
}
int main()
{
    int w, h;

    scanf("%d%d", &w, &h);

    vector<int> valid_states;

    dfs(0, w, 0, valid_states);

    const int m = valid_states.size();

    vector<vector<int>> maps(m);

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if ((valid_states[i] & valid_states[j]) == 0)
            {
                maps[i].push_back(j);
            }
        }
    }

    vector<vector<unsigned long long>> dp(h, vector<unsigned long long>(m, 0));

    for (int i = 0; i < m; ++i)
    {
        dp[0][i] = 1;
    }

    for (int i = 1; i < h; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            for (int ne : maps[j])
            {
                dp[i][j] += dp[i - 1][ne];
            }
        }
    }

    unsigned long long res = 0;

    for (int i = 0; i < m; ++i)
    {
        res += dp[h - 1][i];
    }

    printf("%llu\n", res);

    return 0;
}