描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
当n=1，有1种
当n=2，有2种。
当n=3，三种（3个1，先1后2，先2后1）
当n=3时可以这样看：
如果第一步跳1，剩余两个台阶，两个台阶就是当n=2的总数
否则第一步跳2，剩余一个台阶，一个台阶就是当n=1的总数
S(3)=S(2)+S(1)，S(n)=S(n-1)+S(n-2);斐波那契数列。
function jumpFloor($number)
{
// write code here
$arr = array(1,2);
if($number==1||$$number==2){
return $arr[$number-1];
}
for ($i =2;$i<=$number;$i++){
$arr[$i] = $arr[$i-1]+$arr[$i-2];
}
return $arr[$number-1];
}
题目扩展
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
上述的公式换成S(n)=S(n-1)+S(n-2)+...S(1)+1;(n>3)
function jumpFloorII($number)
{
// write code here
$arr = array(1,2);
if($number==1||$$number==2){
return $arr[$number-1];
}
for ($i =2;$i<=$number;$i++){
for ($j = $i-1;$j>=0; $j--){
$arr[$i] += $arr[$j];
}
$arr[$i] += 1;
}
return $arr[$number-1];
}
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
和上面的问题类似，根据第一块木板横着还是竖着，可以建立类似于斐波那契数列的递推关系。
function rectCover($number)
{
if ($number == 0){
return 0;
}
// write code here
$arr = array(1,2);
if($number==1||$$number==2){
return $arr[$number-1];
}
for ($i =2;$i<=$number;$i++){
$arr[$i] = $arr[$i-1]+$arr[$i-2];
}
return $arr[$number-1];
}
