def climbStairs(n: int) -> int:
if n == 1 or n == 2:
return n
else:
return climbStairs(n-1) + climbStairs(n-2)
print(climbStairs(4))
ZGVmIGNsaW1iU3RhaXJzKG46IGludCkgLT4gaW50OgoJCWlmIG4gPT0gMSBvciBuID09IDI6CgkJCXJldHVybiBuCgkJZWxzZToKCQkJcmV0dXJuIGNsaW1iU3RhaXJzKG4tMSkgKyBjbGltYlN0YWlycyhuLTIpCgkJCQoJCQkKcHJpbnQoY2xpbWJTdGFpcnMoNCkp