【刷算法】我知道的所有類似斐波那契數(shù)列的問題

NotFound 發(fā)布于2019-08-22 18:10 / 3411人閱讀

摘要：有一類算法問題類似斐波那契數(shù)列，而且解決辦法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契數(shù)列跳臺階問題題目描述一只青蛙一次可以跳上級臺階，也可以跳上級。給定整數(shù)，求年后牛的數(shù)量。分析設(shè)為年后牛的數(shù)量，則第年牛的來源有兩個。

有一類算法問題類似斐波那契數(shù)列，而且解決辦法基本差不多。
不了解斐波那契套路的可以看【刷算法】斐波那契數(shù)列

跳臺階問題

題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
分析
設(shè)到第n階總共有f(n)種跳法，而且想跳到第n階只有兩種可能，要么從第n-1階跳一階到達(dá)，要么從第n-2階跳兩階到達(dá)，所以遞推式為f(n)=f(n-1)+f(n-2)。特殊情況為，n=0的時候跳法為0；n=1時，跳法為1；n=2時，跳法為2
遞歸

function jump(n) {
    if(n < 1)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2)
        return 2;
    return jump(n-1) + jump(n-2);
}

非遞歸

function jumpFloor(number)
{
    if(number < 1)   
        return 0;
    if(number === 1)
        return 1;
    if(number === 2)
        return 2;
    var s1 = 1;
    var s2 = 2;
    var res =  0;
    for(var i = 3;i <= number;i++){
        res = s1 + s2;
        s1 = s2;
        s2 = res;
    }
    return res;
}

{{BANNED}}跳臺階問題

題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
分析
{{BANNED}}的跳臺階問題處理起來確實(shí)是有些棘手，一次可以跳上的階數(shù)是不定的。
先看n=0時，跳法f(0)=0；
n=1，只能是從第0個臺階跳過來，跳法f(1)=1;
n=2，可能是第0個臺階跳了2階或者從第1個臺階跳了1階，跳法f(2)=f(0)+f(1);
n=3，可能是第0個臺階跳了3階、第1個臺階跳了2階、第2個臺階跳了1階，跳法f(3)=f(0)+f(1)+f(2);
...
n=n-1，跳法f(n-1)=f(0)+f(1)+f(2)+...+f(n-2);
n=n，跳法f(n)=f(0)+f(1)+f(2)+...+f(n-1);
由上面兩個等式得：f(n) = f(n-1)+f(n-1) = 2f(n-1)
代碼實(shí)現(xiàn)：

function jumpFloorII(number)
{
    if(number < 1)
        return 0;
    if(number === 1)
        return  1;
    return 2*jumpFloorII(number-1)
}

矩陣覆蓋

題目描述
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？
分析
ps：為了方便分析問題，給每個小矩形不同的顏色，其實(shí)他們之間沒有差別

假設(shè)上圖為用n個21的小矩形無重疊地覆蓋一個2n的大矩形，方法數(shù)為f(n)，那么f(n)可以從哪些情況推導(dǎo)出來呢？
首先很明顯我們知道，2*1的小矩形要么是橫著放要么是豎著放，所以f(n)的情況只能由以下兩種情況得來：

這種情況只需要再加一個豎著的小矩形就可以了，所以這種情況其實(shí)是f(n-1)

這種情況下，只需要再加一個橫著的小矩形就可以了，但是由于這種橫著的小矩形只能成對出現(xiàn)，所以這種情況其實(shí)是f(n-2)
綜上，f(n) = f(n-1)+f(n-2)
特殊情況時，f(0)=0，f(1)=1，f(2)=2
代碼實(shí)現(xiàn)
遞歸版

function rectCover(n)
{
    if(n === 0)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2)
        return 2;
    return rectCover(n-1) + rectCover(n-2)
}

非遞歸版

function rectCover(n)
{
    if(n === 0)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2)
        return 2;
    var s1 = 1, s2 = 2;
    var res = 0;
    for(var i = 3;i <= n;i++) {
        res = s1 + s2;
        s1 = s2;
        s2 = res;
    }
    
    return res;
}

母牛生小牛問題

題目描述
假設(shè)農(nóng)場中成熟的母牛每年只會生一頭小母牛，且永遠(yuǎn)不會死。第一年農(nóng)場有1頭成熟的母牛，從第二年開始，母牛開始生小母牛，每只小母牛3年之后成熟又可以生小母牛。給定整數(shù)N，求N年后牛的數(shù)量。
分析
設(shè)f(n)為n年后牛的數(shù)量，則第n年牛的來源有兩個。
首先，牛是永遠(yuǎn)不會死的，所以第n-1的牛都會活到第n年；
其次，還有一部分新生的牛，因?yàn)槊恐恍∧概?年之后成熟才可以生小母牛，所以第n-3年的未成熟小母牛到了第n年會成熟且開始生小母牛，所以第n年新生的牛來自于第n-3年的未成熟小母牛和成熟母牛。
綜上，f(n) = f(n-1) + f(n-3)
特殊的，f(1)=1，f(2)=2，f(3)=3
代碼實(shí)現(xiàn)
直接非遞歸版

function cow(n) {
    if(n < 1)
        return 0;
    if(n === 1)
        return 1;
    if(n === 2) 
        return 2;
    if(n === 3)
        return 3;
    var s1 = 1, s2 = 2, s3 = 3;
    var res = 0;
    for(var i = 4;i <= n;i++){
        res = s1+s3;
        s1 = s2;
        s2 = s3;
        s3 = res;
    }
    
    return res;
}