leetcode with python:70. Climbing Stairs

题目:

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

你可以一次爬1或2阶楼梯,那爬n阶楼梯的方式有几种

我们可以把方法归类成两种,最后一步爬一阶跟最后一步爬二阶
即爬n-1阶的方法数+爬n-2阶的方法数加起来就是爬n阶的方法数
我们可以列式:f(n)=f(n-2)+f(n-1)
我们发现这其实就是个类费波那契数列（Fibonacci sequence）的结构
只要知道f(1),f(2)就能推断出其他f(n)
而我们知道f(1)=1(一次一阶),f(2)=2(一次二阶和两次一阶)便可以开始实作了

class Solution:    def climbStairs(self, n: int) -> int:        ans=[1,2]        for i in range(2,n):            ans.append(ans[-1]+ans[-2])        return ans[n-1]

建立一个阵列,第n项即代表f(n)的值
先将f(1),f(2)放入阵列,之后append的新项为末两项和
直到append到第n项(即得知了我们要的f(n))
就回传我们算出的f(n)值
不用递迴是因为複杂度来到O(2^n),容易超时
最后执行时间24ms(faster than 98.81%)

那我们下题见