网站建设验收条款,业务多平台怎么样,云呼叫中心系统 免费,免费的软件大全下载文章目录 力扣70 爬楼梯示例代码实现总结收获 力扣70 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 代码实现
class Solution {Map Integer,Integer mapnew HashMap();p… 文章目录 力扣70 爬楼梯示例代码实现总结收获 力扣70 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 代码实现
class Solution {Map Integer,Integer mapnew HashMap();public int climbStairs(int n) {if(n1)return 1;if(n2)return 2;if(map.containsKey(n))return map.get(n);int sum climbStairs(n-1)climbStairs(n-2);map.put(n,sum);return sum;}
}//f(n)f(n-1)f(n-2) f(1)1 f(2)2总结收获
这道题很显然属于斐波那契数列的一个变体所以第一想法是使用递归去做。于是很容易得到公式f(n)f(n-1)f(n-2) f(1)1 f(2)2是一个多路递归。但是如果单纯递归这道题会超时所以还需要加上一个备忘录通过map将之前出现的值存储一下这个也就是递归优化-记忆法
