题目

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.

解题思路

1个台阶有1种方案
2个台阶有2种方案
3个台阶有3=2+1种方案
...
n个台阶有f(n) = f(n-1) + f(n-2)种方案

使用递归的话会超时，所以使用循环计算

代码

func climbStairs(n int) int {
    if 1 == n {
        return 1
    } else if 2 == n {
        return 2
    }
    

    ret1 := 1
    ret2 := 2
    var ret int
    for i := 2; i < n; i++ {
        ret = ret1 + ret2
        ret1 = ret2
        ret2 = ret
    }
    
    return ret
}