一个青蛙跳台阶的变种问题，半天写不出来

Question

宇宙中有 n 个一样的星球，灭霸一次能灭一个或者两个星球，但是一次灭两个星球之后的两次每次只能灭一个星球，请问灭霸有多少种方式灭完 n 个星球。

Answer 1

斐波那契额数列

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

n = int(input())
print(fib(n))