说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。
题目来源
- 分类：递归
- 矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路
参考学习：[Daniel Lee]
https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6
用归纳法归纳如下，
- 当 n < 1时，显然不需要用2*1块覆盖，按照题目提示应该返回 0；
- 当 n = 1时，只存在一种情况；
- 当 n = 2时，存在两种情况。|| 或者 =；
- 当 n = 3时，在n = 2 的基础上进行添加 ||| ，=|， |=
- 当 n = 4时，在n = 3 的基础上进行添加 |||| ，=||， |=|，之后新增加的21 方块与临近的21方块组成 2*2结构，然后可以变形成 “=”。于是 n = 4在原来n = 3基础上增加了||=、==；
所以，自然而然可以得出规律： f(n) = f(n-1) + f(n-2)， (n > 2)。
相应的结论应该是： - 1 * 3方块 覆 盖3*n区域：f(n) = f(n-1) + f(n - 3)， (n > 3)
- 1 4 方块 覆 盖4n区域：f(n) = f(n-1) + f(n - 4)，(n > 4)
更一般的结论，如果用1m的方块覆盖mn区域，递推关系式为f(n) = f(n-1) + f(n-m)，(n > m)。
编程实现
PHP
<?php
// 运行时间：28ms 占用内存：3664k
function rectCover($number)
{
if ($number <= 0){
return 0;
}
if ($number == 1 || $number == 2){
return $number;
}
$f1 = 1;
$f2 = 2;
while($number > 2){
$temp = $f1 + $f2;
$f1 = $f2;
$f2 = $temp;
$number--;
}
return $temp;
}
// 递归
function rectCover($number)
{
if ($number <= 0){
return 0;
}
if ($number == 1 || $number == 2){
return $number;
}
return rectCover($number - 1) + rectCover($number - 2);
}
?>
Python
# -*- coding:utf-8 -*-
class Solution:
# 可以使用和php相同的办法，这里使用一个新的思路，使用数组
def rectCover(self, number):
num = []
num.append(0)
num.append(1)
num.append(2)
for i in range(3, number + 1):
num.append(num[i-1] + num[i-2])
return num[number]
s = Solution()
print s.rectCover(6)
