剑指Offer - PHP矩形覆盖
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
比如n=3时，2*3的矩形块有3种覆盖方法：
分析
| 小矩形数量n | 大矩形面积2*n | 总的方法数res |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 2*1 | 1 |
| 2 | 2*2 | 2 |
| 3 | 2*3 | 3 |
| 4 | 2*4 | 5 |
| 5 | 2*5 | 8 |
从 n=3 开始，其res等于前两次的和。所以求n块矩形总共有多少种方法时，只需要知道前两次的值，将前两次相加即可。
所以使用一个数组来保存前两次的值，循环更新数组即可。
代码
<?php
function rectCover($number)
{
if($number < 1) return 0;
$tmp = [0,1]; // 初始值
for($i = 1; $i <= $number; $i++) {
$res = $tmp[0] + $tmp[1];
$tmp[0] = $tmp[1];
$tmp[1] = $res;
}
return $res;
}
关于 LearnKu
粤公网安备 44030502004330号