杭电acm2046水题求解

题目

杭电acm2046水题求解
我看到很多大神都是使用斐波那契数列解决问题的,我想问下,什么思路与想法联想到斐波那契数列的呢?
Problem Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图：
Input
输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0

答案

把大问题化成小问题对在2*n个方格内放牌 每一个牌只有两种放法如果竖着放 问题就转化成在2*(n-1)个方格有多少种放牌方法如果横着放 必须一次放两个牌 问题就变成在2*(n-2)个方格有多少种放牌方法所以answer(2*n)=ans...