【解题报告】【lintcode111】Climbing Stairs

题意

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

解答

由于一次只能走一步或者两步,所以我们可以直接获得递归的公式,但是当楼梯太多的时候,递归层次太深,会超时。
我们又想到dp,由于一次走一步或者两步,所以可以从上一个状态或者上两个状态到达当前状态,所以可以得到公式
dp[n] = dp[n-1]+dp[n-2]
因为对于dp[n-1]来说,只能走一步,对于dp[n-2]只能走长度2,所以我们把他们的解的个数加起来,就是我们现在的解数了。

代码

u3coding

A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*