一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階墓陈。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法腮恩。
答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008偏窝，請返回 1。
鏈接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
示例 1：
輸入：n = 2
輸出：2
示例 2：
輸入：n = 7
輸出：21
示例 3：
輸入：n = 0
輸出：1
提示：
0 <= n <= 100
思路：
（1）回溯（遞歸）
a. DP狀態(tài)的定義： f(n)表示到底n階的總走法個(gè)數(shù)
b. DP方程的推導(dǎo)：f(n) = f(n-1) + f(n-2) f(0) = f(1) = 1
（2）時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(1) for i-2 -->n
（3）log(n)解法.....
- 解法1
func numWays(n int) int {
if n == 0 {
return 1
}
if n == 1 || n == 2 {
return n
}
mem := make([]int, n)
mem[0] = 1;
mem[1] = 2;
for i := 2; i < n; i++ {
mem[i] = mem[i-1] + mem[i-2]
mem[i] %= 1000000007
}
return mem[n-1]
}
- 解法2
func numWays(n int) int {
if n < 0 {
return 0
}
if n == 0 {
return 1
}
if n <= 2 {
return n
}
res := 1
pre := 1
for i := 2; i <= n; i++ {
pre, res = res, (res + pre) % 1000000007
}
return res
}
