[剑指-10](php&python):矩形覆盖

说明：记录刷剑指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)