蒙德里安的梦想 Python 动态规划
题目描述
求把 N×M
的棋盘分割成若干个 1×2
的长方形,有多少种方案。
样例
输入
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出
1
0
1
2
3
5
144
51205
算法1
(动态规划) 指数级别
先摆放横的小方块,那么剩下摆竖的方案数只有一种
即总方案数量就是横着放的方案数量
要求每一列连续空着的小方块,要是偶数个
-
状态表示:
f(i, j), 表示将前i-1列摆好,从第i-1列伸出到第j列,状态是j的所有方案数量
j是一个二进制数,但我们用十进制数来存储 -
状态计算:
考虑已经摆放好的前i-1列,第i-1列的状态k,第i-2列是伸向i-1列还是不伸,所以共$2^n$种可能, -
约束:
假设伸到i-1列的状态是k,则 j & k == 0, 表示不重叠,同时要求对于第i-1列,连续空着的位置长度必须为偶数 -
优化
预处理st数组:判断某二进制序列是否有偶数个0
处理status数组:在st的基础上,继续判断是否重叠,单位是二进制序列
至此,已经将朴素的$2^k$个类别规约到合法的类别,在此基础上求和即可
$f[i, j] = f[i - 1, 合法k]$
时间复杂度 指数级别
子问题数量$n * 2^n$,求解子问题要$O(2^n)$
(j代表的二进制序列共$2^n$种可能,即状态计算的时候要分为$2^n$类)
Python 代码
N = 12
M = 1 << N # 2^12
f = [[0] * M for i in range(N)] #状态数组
state = [[] for i in range(M)] # 序列合法数组,既满足0为偶数也满足伸出方块在第i-1列不重叠
st = [True] * M # 序列奇偶合法数组st,代表哪种二进制序列包含偶数个0
#预处理st
while True:
n, m = map(int, input().strip().split())
if not n and not m:
break
# 伸或不伸共2^n种可能
for i in range(1 << n):
cnt = 0
is_valid = True
for j in range(n): # 二进制下的i共n位
if (i >> j) & 1: # 逢1判断以上0的个数奇偶
if cnt & 1:
is_valid = False
break
cnt = 0
else:
cnt += 1
# 最后一段0可能遇不上1,要额外做判断
if cnt & 1:
is_valid = False
st[i] = is_valid
# 处理合法序列数组state
for i in range(1 << n):
state[i].clear()
# 二进制序列还是用十进制数来表示,如j= 00100 = 4
for j in range(1 << n):
if not (i & j) and st[i | j]: #用二进制序列位运算,判断不在同一行,且奇偶合法
state[i].append(j)
#至此,状态计算中,已经把所有2^n种可能的序列j,缩小至合法的序列,即state[i]元素个数了
#清空数组,否则上一轮影响这次f[][]
f = [[0] * M for i in range(N)]
#状态计算
f[0][0] = 1
for i in range(1, m + 1):
for j in range(1 << n):
for k in state[j]:
#在合法序列里计算,计数DP,又有点像完全背包的划分方式
f[i][j] += f[i - 1][k]
#最优值
print(f[m][0])