状态压缩动态规划 -- 多米诺骨牌

本文主要是介绍状态压缩动态规划 -- 多米诺骨牌，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用1*2 的骨牌通过组合拼成 m * n 的大矩形，问有几种拼法。

题目链接：http://poj.org/problem?id=2411

状态转移：

1.由于上一行的该列竖直放置骨牌为 0，影响到当前行的该列，当前行的该列为 1

2.当前行骨牌横放，上一行骨牌横放， 都为11

3.上一行该列置为 1，当前行当前列立着放为 0

#include <iostream>
#include <cstring>
using namespace std;
#define MAXSIZE 12
int cols, raws;
int col, raw;
long long DP[MAXSIZE][( 1 << MAXSIZE ) - 1];void search( int col, int cur, int pre ){if( col >= cols ){if( col == cols ){DP[raw][cur] += DP[raw - 1][pre];}return;}search( col + 1, cur << 1, pre << 1 | 1 );search( col + 1, cur << 1 | 1, pre << 1 );search( col + 2, cur << 2 | 3, pre << 2 | 3 );
}int main(){while( cin >> raws >> cols ){if( raws == 0 && cols == 0 )break;if( cols > raws ){raws = raws ^ cols;cols = raws ^ cols;raws = raws ^ cols;}memset( DP, 0, sizeof( DP ) );DP[0][( 1 << cols ) - 1] = 1;for( raw = 1; raw <= raws; ++raw )search( 0, 0, 0 );cout << DP[raws][( 1 << cols ) - 1] << endl;}return 0;
}

这篇关于状态压缩动态规划 -- 多米诺骨牌的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---