關(guān)于爬樓問題的最優(yōu)算法實現(xiàn)

爬樓問題：假設(shè)有一段n階的樓梯，每次可以爬1階或者2階，問：共有多少種爬樓方式.

分析問題：假設(shè)n階樓梯的爬樓方式有f(n)種
當(dāng)n=1時，得到f(1)=1;
當(dāng)n=2時，得到f(2)=2;
當(dāng)n>2時,如果第一步走1步的話則有f(n-1)種方式，如果第一步走2步的話則有f(n-2)種，所以可得:f(n)=f(n-1)+f(n-2);

分析完畢，接下來就是代碼的實現(xiàn)了。
方案一:
由分析很容易想到遞歸的方式來設(shè)計代碼.設(shè)計代碼如下:

unsigned long stepWays(unsigned long num){
    if (num == 1) {
        return 1;
    }
    if (num == 2) {
        return 2;
    }
    return stepWays(num-1)+stepWays(num-2);
}

運行一下代碼測試一下

NSDate *date = [NSDate date];
printf("方案一有%lu種方式",stepWays(45));
NSTimeInterval time = date.timeIntervalSinceNow*-1;
printf("\n耗時:%lfs",time);

結(jié)果如下：

方案一有1836311903種方式
耗時:6.249614s

考慮到時間和空間復(fù)雜度的問題，顯然遞歸并不是一個好的算法解決方案。所以考慮到不使用遞歸的方案二來實現(xiàn)。
方案二:
根據(jù)f(n)=f(n-1)+f(n-2)表達式，設(shè)計代碼如下：

unsigned long stepWays2(unsigned long num){
    if (num == 1) {
        return 1;
    }
    if (num == 2) {
        return 2;
    }
    unsigned long n = 3;
    unsigned long n1 = 1;//f(n-2)
    unsigned long n2 = 2;//f(n-1)
    unsigned long res = 0 ;//f(n)
    while (n <= num) {
        res = n1 + n2;
        n1 = n2;
        n2 = res;
        n ++;
    }
    return res;
}

很明顯方案二這種設(shè)計在復(fù)雜度上來說是最優(yōu)的。驗證一下：

NSDate *date = [NSDate date];
printf("方案二共有%lu種方式",stepWays2(45));
NSTimeInterval time = date.timeIntervalSinceNow*-1;
printf("\n耗時:%lfs",time);

輸出如下：

方案二共有1836311903種方式
耗時:0.000023s

驗證方案二為最優(yōu)解

Demo