du熊填数字

http://star.baidu.com/index.php?r=home/detail&id=3

看一张图片就知道怎么做了

四个角是等价的

将直角拉直，问题转换为求长度为x的01序列的方案数，要求不能有两个相邻的1