1665: 4.5算法之动态规划

1665:完美覆盖

在一个标准的国际象棋棋盘上共有64个方格（由8行8列组成）。每张多米诺骨牌都具有相同的形状，并且每枚骨牌恰好能够覆盖相邻两块方格中的任意两个（即一张骨牌占据一行两列的位置或者两行一列的位置）。那么请问：能否将32枚这样的骨牌精确地放置在该棋盘上而不发生重叠，并且能够完全覆盖整个棋盘的所有区域？这个问题属于一种经典的排列组合问题；通过手动尝试也可以迅速想出多种不同的完美铺排方式。然而，在计算所有可能的不同完美铺排总数时确实有一定难度。现在我们利用计算机编程的方法来解决这一问题。

任务：请编写一段代码实现以下功能：对 3×n 棋盘的所有不同完美覆盖方案的数量进行计算

输入：每次输入可能包含若干行数据（即 3×n 棋盘的列数 n），当用户键入 -1 时程序终止

对于每一个n值所在的行来说，请提供一个关于3 \times n棋盘的不同完美覆盖数量的结果。

请提供以下各个数值对应的完美覆盖数量：

输入：

输出：

分析：

<>

设a[i]为N=i时的方法数.i为奇数的时候肯定为0.

假设i是一个偶数，则a[i]