剑指offer——铺地板

剑指offer——铺地板

题目描述

我们可以用2x1的小矩形（下左）去横着或竖着覆盖更大的矩形，请问用8个2x1的小矩形无重叠覆盖一个2x8的大矩形（下右），共有多少种方法？

解题思路：

从左边起覆盖，

若第一次小矩形横着覆盖，有f(6)种方法，

若第一次小矩形竖着覆盖，有f(7)种方法，

即f(n) = f(n-1) + f(n-2)

也是属于斐波那契数列

    int solve(int n){int res[] = {0,1};if(n < 2) return res[n];int fa = 1, fb = 1, fn = 0;for(int i = 2; i <= n; i++){fn = fa + fb;fa = fb;fb = fn;}return fn;}