70. Climbing Stairs

Description

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

Answer

这道题会引发出来很多思考，解法很多，下面的是我提交的方式 O（n）O(1)，还有更优的答案O(logn),O(1)，后续会单独分析

package main

import "fmt"

func climbStairs(n int) int {
    if n == 0 {
        return 0
    }

    var sum int
    if n <= 1 {
        return 1

    }
    tempa := 1
    if n <= 2 {
        return 2

    }
    tempb := 2

    for i := 3; i <= n; i++ {
        sum = tempa + tempb
        tempa = tempb
        tempb = sum
    }

    return sum
}

func main() {

    fmt.Println(climbStairs(4))

}