关于爬楼问题的最优算法实现

关于爬楼问题的最优算法实现

爬楼问题：假设有一段n阶的楼梯，每次可以爬1阶或者2阶，问：共有多少种爬楼方式.

---

分析问题：假设n阶楼梯的爬楼方式有f(n)种
当n=1时，得到f(1)=1;
当n=2时，得到f(2)=2;
当n>2时,如果第一步走1步的话则有f(n-1)种方式，如果第一步走2步的话则有f(n-2)种，所以可得:f(n)=f(n-1)+f(n-2);

分析完毕，接下来就是代码的实现了。
方案一:
由分析很容易想到递归的方式来设计代码.设计代码如下:

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);

结果如下：

方案一有1836311903种方式
耗时:6.249614s

考虑到时间和空间复杂度的问题，显然递归并不是一个好的算法解决方案。所以考虑到不使用递归的方案二来实现。
方案二:
根据f(n)=f(n-1)+f(n-2)表达式，设计代码如下：

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;
}

很明显方案二这种设计在复杂度上来说是最优的。验证一下：

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

输出如下：

方案二共有1836311903种方式
耗时:0.000023s

验证方案二为最优解

Demo