斐波那契相关问题

描述

一只青蛙一次可以跳上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];
}