题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入格式

一个整数。

输出格式

一个整数。

输入/输出样例

输入1

2

输出1

2

 

 解题思路：

这是一个经典的动态规划问题，也可以看作是斐波那契数列的一种变种。

假设到达第 n 阶楼顶的方法数为 f(n)，那么 f(n) 可以由 f(n-1) 和 f(n-2) 两种方式组成，
即一次爬 n-1 阶，或者一次爬 n-2 阶。

因此，可以得到递推公式：f(n) = f(n-1) + f(n-2)。

同时，我们知道到达第一阶和第二阶的方法数分别为 f(1) = 1，f(2) = 2（一次爬一阶或两阶）。

接下来，我们可以用动态规划的方式，从下到上计算出 f(n)，即先计算出 f(3)=1+2=3，f(4)=2+3=5，...，f(n)。

最终，f(n) 就是我们要求的结果，即到达楼顶的不同方法数。

python解：

def pa(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return pa(n-1)+pa(n-2)

n=int(input())
print(pa(n))