slt

思路1 dp

时间复杂度 O(n) 空间复杂度 O(n)

为方便，我们把楼梯按索引的方式也从0开始。 dp[i]表示到i层有多少中方法，显然dp[0]=1, dp[1]=2。当i>=2时，到达i可以从i-1,i-2两种方法。因此有dp[i] = dp[i-1] + dp[i-2];

思路2 dp 压缩存储空间

时间复杂度 O(n) 空间复杂度 O(1)

应注意到这道题和斐波那契数列的关系。类似Unique path 62和min path sum 64中那样，这道题也可以压缩存储空间。