DP2 题解 | #跳台阶#

#这就要比DP1难一点了，因为dp含义、递推公式都没有直接给出来
#动态规划五部曲：确定dp含义、写出递推公式、初始化、遍历、打印debug

#dp[i]表示青蛙跳上第i个台阶的跳法
n=int(input())
dp=[0 for i in range(40)]

#递推公式，由题可知：第i级台阶可由第i-1或第i-2级台阶得到
#故dp[i]=dp[i-1]+dp[i-2]

#严格来讲，dp[0]应该是无意义的，dp[1]等于1，dp[2]=2
dp[1]=1
dp[2]=2

#遍历
for i in range(3,n+1):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])