杭电acm2046水题求解我看到很多大神都是使用斐波那契数列解决问题的,我想问下,什么思路与想法联想到斐波那契数列的呢?ProblemDescription在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,

Question

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

Answer 1

把大问题化成小问题
对在2*n个方格内放牌 每一个牌只有两种放法
如果竖着放 问题就转化成在2*(n-1)个方格有多少种放牌方法
如果横着放 必须一次放两个牌 问题就变成在2*(n-2)个方格有多少种放牌方法
所以answer(2*n)=answer(2*(n-1))+answer(2*(n-2))
把2去掉就变成ans(n)=ans(n-1)+ans(n-2)
初始条件answer(2*1)=1 answer(2*2)=2
就是斐波那契数列