LeetCode 70. Climbing Stairs

题目

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1.1 step + 1 step
2.2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1.1 step + 1 step + 1 step
2.1 step + 2 steps
3.2 steps + 1 step

解析

题目意思是比较好理解的，是一个正数n中，只有1和2两种累加，求解多少种方法，不妨先用数学推导一下。

n    ways
1    1
2    2
3    3
4    5
...
n    F(n)

当n=4时，其情况有

1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
共5种情况

因此，F(n) = F(n-1) + F(n-2)，意义是，F(n)是由第n-1阶走1步和第n-2阶走2步上来，两种情况的累加。这是斐波那契数列。再编写代码就很简单了。

代码

int climbStairs(int n) {
    if (n == 1 || n == 2)
        return n;
    
    int prior = 1, behind = 2, ways = 0;
    
    for (int i = 3; i <= n; ++i) {
        ways = prior + behind;
        
        prior = behind;
        behind = ways;
    }
    
    return ways;
}

n=1和n=2的情况直接返回n1和2。从3开始，设置prior为F(n-2)，behind为F(n-1)，依次赋值，最终得到ways方式数量。