【python】蒙德里安的梦想——状态压缩dp

求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。 例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3
时，共有 3 种方案。 如下图所示：

输入格式
输入包含多组测试用例。 每组测试用例占一行，包含两个整数 N 和 M。 当输入用例 N=0，M=0
时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个结果，每个结果占一行
数据范围
1≤N,M≤11
输入样例
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

# 以下有C语言改写
while True:
    n, m = map(int, input().split())
    st = [True for i in range(1 << n)]  # st用来存放该状态是否合法 比如1101就不合法，所以st[13]=False
    if n == 0 and m == 0:  # 退出程序
        break

    '''
    出现0的次数为奇数则不合法 这里的出现是连续的 比如0110就不合法，因为0不连续
    '''
    # 判断是否合法
    for i in range(1 << n):
        st[i] = True
        count = 0  # 计算0的次数
        for j in range(n):
            if i >> j & 1:  # 如果是1，说明连续0结束
                if count & 1:  # 如果count是1，说明是奇数
                    st[i] = False
                    break
            else:
                count += 1
        if count & 1:
            st[i] = False

    # 状态转移
    dp = [[0] * (1 << n) for _ in range(m + 1)]
    dp[0][0] = 1
    for i in range(1, m + 1):  # 枚举列 遍历列
        for j in range(1 << n):  # 枚举当列状态
            for k in range(1 << n):  # 枚举上一列的状态
                if j & k == 0 and st[j | k]:  # 与上一列合并 如果相与不为0 说明重复摆放  如果st为False则有奇数0 都不合法
                    dp[i][j] += dp[i - 1][k]  # 状态转移方程

    # 最后一列不可能摆得下1了 所以为0
    print(dp[m][0])

基本每一行代码都有注释，应该可以看得懂的吧~
看不懂的欢迎留言，我每天都会来看的！