[LeetCode刷题笔记] 070爬楼梯

1-题目要求

2-题目分析

对于菜鸟的我来说,是完全不知道这道题在考察什么的,完全没有下手的思路.
这倒是真实地反映了我太久不思考数学问题丧失了抽象思维的本质.
考点是斐波那契数列
我们每次可以爬楼梯一次或者爬楼梯两次.假设我们现在开始爬第n次楼梯,那么它一共可能有多少种可能呢?
我们来看我们第n-1次的情况,一共有两种可能,无非是n-1次的时候是走了一阶楼梯到达了n,或者n-1次走了两阶楼梯到达了n.
所以符合斐波那契数列的定义$F(n)= F(n-1)+F(n-2)$F(n)=F(n−1)+F(n−2)

3-解题

既然知道这是一道考察斐波那契数列的题目了,那就很简单了.
下次刷算法题如果没有思路,可以看看题目标签

int climbStairs(int n)
{    int i; //这里的i用来设置循环      
     unsigned long m[3];//假设当前循环为第k级,这个数组用于记录到达第k-1级的走法    
     // 根据题意可知,当i=1的时候,有1种走法,到i=2的时候,有两种走法    
     if(n == 1) return 1;    
     if(n == 2) return 2;    
     m[0] = 0; m[1] = 1; m[2] = 2;    // 用m[0]来记录中间的变化 当n=3的时候就等于 m[1] + m[2]    
     // 即走三阶楼梯就等于走两阶楼梯之后再走一阶楼梯    // 那么我们用m[1]和m[2]存放这两种可能    
     // 从i = 3 开始 就要进行累加移动了    
     for(i = 3; i <= n; i++)    
     {        
         m[0] = m[2]; // 用 m[0] 临时存储后一阶段的值        
         m[2] = m[1] + m[2]; // 这时候 m[2] 计算得到这次的结果        
         m[1] = m[0]; // 让 m[1] 读取 m[0] 存储的值        
     }    
     return m[2];
}