剑指offer 07 跳台阶
2020-02-14 本文已影响0人
洛珎
题目：
image.png
思路：
1.递归方法：满足斐波那列数列，return dp[n-1] + dp[n-2];不建议这样做，这样会重复计算，效率低，占据空间大
2.动态规划解决：不管n级台阶有几种跳法，对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，因此只需要求出到达n-1级台阶方法和n-2阶台阶方法即可，dp[i] = dp[i-1]+dp[i-2],会把计算的结果记录下来，而递归不会记录，效率低
代码：
image.png
递归和动态规划的区别
image.png
