題目

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)種方案

使用遞歸的話會超時，所以使用循環(huán)計算

代碼

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
}