侯先生每天都会爬楼梯锻炼身体，他有时候一次上跨一级，有时候一次上跨两级...有一天侯先生想弄明白一个很难的问题：从最下面的第1级开始到顶端的第n级一共有多少种走法呢？比如n是3时，有两种走法（或者直接从第1级上跨两步到第3级，或者从第1级跨一步到2级再跨一步到第3级）。‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬ 请你帮帮侯先生，给你n（1<n<40）的值，你帮忙计算并输出有多少种爬到顶端的方法。

这是一道典型的动态规划问题，可以用一个数组记录从第1级到第i级的走法数目，然后利用递推公式计算出从第1级到第n级的走法数目。

具体来说，设dp[i]表示从第1级到第i级的走法数目，那么有以下递推公式：

dp[i]=dp[i-1]+dp[i-2]

其中dp[1]=1, dp[2]=2。

最终的答案就是dp[n]。

以下是Python代码实现：

n = int(input())
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])