题目描述
动态规划这里可以推得递推公式为，要注意，当跳到
f
(
n
−
2
)
f(n-2)
f(n−2)时，本来可以有两种方式跳到
f
(
n
)
f(n)
f(n)，但一步一步跳的方式与从
f
(
n
−
1
)
f(n-1)
f(n−1)跳到
f
(
n
)
f(n)
f(n)的方式重复，因此也只有一种方式
f
(
n
)
=
f
(
n
−
1
)
+
f
(
n
−
2
)
f
(
0
)
=
f
(
1
)
=
1
f(n)=f(n-1)+f(n-2)\ f(0)=f(1)=1
f(n)=f(n−1)+f(n−2)f(0)=f(1)=1
class Solution:
def numWays(self, n: int) -> int:
# 递推公式：f(n) = f(n-1) + f(n-2), f(0)=f(1)=1
if n <= 1:
return 1
p, q, res = 0, 1, 1
for i in range(2, n+1):
p = q
q = res
res = (p + q) % (10**9+7)
return res
