剑指 Offer 10- II. 青蛙跳台阶问题
//滚动数组,空间O1
func numWays(n int) int {
prev , cur := 1, 1
for i := 2; i <= n; i++ {
temp := (cur + prev) %1000000007
prev = cur
cur = temp
}
return cur
}
//时空都是On
func numWays(n int) int {
if n==1||n==0{
return 1
}
if n==2{
return 2
}
dp := make([]int, n+1)
dp[0], dp[1] = 1, 1
for i := 2; i <= n; i++ {
dp[i] = (dp[i-1] + dp[i-2]) %1000000007
}
return dp[n]
}