带有备忘录的递归算法
2021/10/31 17:39:40
本文主要是介绍带有备忘录的递归算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
暴力递归
★ leetcode原题:一只青蛙一次可以跳上1级台阶,也可以跳上2级台 阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。
- 要计算原问题 f(10),就需要先计算出子问题 f(9) 和 f(8)
- 然后要计算 f(9),又要先算出子问题 f(8) 和 f(7),以此类推。
- 直到 f(2) 和 f(1),递归树才终止。
要想跳到第10级台阶,要么是先跳到第9级,然后再跳1级台阶上去;要么是先跳到第8级,然后一次迈2级台阶上去。
同理,要想跳到第9级台阶,要么是先跳到第8级,然后再跳1级台阶上去;要么是先跳到第7级,然后一次迈2级台阶上去。
要想跳到第8级台阶,要么是先跳到第7级,然后再跳1级台阶上去;要么是先跳到第6级,然后一次迈2级台阶上去。
1 普通的递归算法
class Solution { public int numWays(int n) { if(n == 1){ return 1; } if(n == 2){ return 2; } return numWays(n-1) + numWays(n-2); } }
2 带备忘录的递归算法
带备忘录的递归算法,子问题个数=树节点数=n,解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。接下来呢,我们用带备忘录的递归算法去撸代码,解决这个青蛙跳阶问题的超时问题咯~,代码如下:
public class Solution { //使用哈希map,充当备忘录的作用 Map<Integer, Integer> tempMap = new HashMap(); public int numWays(int n) { // n = 0 也算1种 if (n == 0) { return 1; } if (n <= 2) { return n; } //先判断有没计算过,即看看备忘录有没有 if (tempMap.containsKey(n)) { //备忘录有,即计算过,直接返回 return tempMap.get(n); } else { // 备忘录没有,即没有计算过,执行递归计算,并且把结果保存到备忘录map中,对1000000007取余(这个是leetcode题目规定的) tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007); return tempMap.get(n); } } }
这篇关于带有备忘录的递归算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南