Leetcode-70-climbing-stairs | 爬楼梯

题目链接

• leetcode中国

解题思路

解法一

第一层：0+1=1种
第二层：1+1=2种
第三层：2+1=3种
第四层：3+2=5种
第五层：5+3=8种
第六层：8+5=13种
…

得出结论：第x层爬楼梯的方法数量=第x-1层种+第x-2层种

func climbStairs(n int) int {
    if n <= 2 {
        //小于2，直接返回值
        return n
    }

    FirstNum := 1
    SecondNum := 2
    result := 0
    for i:=3;i<=n;i++ {
        result = FirstNum + SecondNum  //当前层 = 倒数第一层 + 倒数第二层
        FirstNum = SecondNum
        SecondNum = result
    }

    return result
}

动态规划

转移方程：f(x)=f(x−1)+f(x−2)

func climbStairs(n int) int {
    p, q, r := 0, 0, 1
    for i := 1; i <= n; i++ {
        p = q
        q = r
        r = p + q
    }
    return r
}