精华内容
下载资源
问答
  • 记忆化递归

    2020-08-02 09:36:19
    记忆化递归 ​ 在递归的过程中难免会存在相同的值,相同的计算过程,那么重复的计算难免会浪费资源。因此将这类值存储起来,在递归的过程中使用,这样的过程称为记忆化递归。 递归例子 ​ 一只青蛙每次能跳1级或者2...

    记忆化递归

    ​ 在递归的过程中难免会存在相同的值,相同的计算过程,那么重复的计算难免会浪费资源。因此将这类值存储起来,在递归的过程中使用,这样的过程称为记忆化递归。

    递归例子

    ​ 一只青蛙每次能跳1级或者2级的台阶,现在计算跳到n级台阶的跳法有多少种?

    分析

    ​ 对于n级台阶而言,青蛙倒数最后第二次,一定跳到的是n-1,或者是n-2的台阶。跳到n-1或者n-2的跳法数相加便是跳到n级的跳法数。那么套娃递归公式就出来了
    f(n)=f(n1)+f(n2) f(n)=f(n-1)+f(n-2)
    ​ 如果为5级台阶

    																				      5
    																		  4         			 3
    																 3			    2        2               1
    															 1            2 
    

    ​ 由此得出n-k = 1或者2是为结束条件,跳1阶台阶跳法为1种,2阶台阶跳法为2种

    代码

    function step(n){
        if(n==2){
            return 2
        }
        if(n==1){
            return 1
        }
        return step(n-1)+step(n-2)
    }
    
    //测试
    let pre = process.uptime();
    console.log('跳法:',step(5))   //8种
    let err = process.uptime() - pre;
    console.log(err * 1000)
    

    递归优化

    ​ 在以上例子中,对于5级台阶,每次都需要重复计算相同台阶的跳法,这样使得效率很低。

    ​ 因此可以使用空间换取效率

    let cache = [, 1, 2]
    function step(n) {
        if (!cache[n] && cache[n] != 0) {
            cache[n] = step(n - 1) + step(n - 2);
        }
        return cache[n]
    }
    
    //测试
    let pre = process.uptime();
    console.log('跳法:',step(70))
    let err = process.uptime() - pre;
    console.log(err * 1000)
    

    前后结果对比

    ​ n = 100

    ​ 未优化,时间太长

    ​ 优化后,10m以内

    展开全文
  • 记忆化递归问题

    2021-04-21 15:40:50
    记忆化递归

    记忆化递归的原理和思路

    为什么要用记忆化递归?

    回答:因为普通的递归可能会重复求解某一值,类似斐波那契数列。同样的子问题可能会被求解多次,这样就会很慢很慢很慢。

    解决方法:我们把历史求解(子问题)记录下来,如果下次需要求解子问题,那么直接取出就好。其时间复杂度为O(1)。

    举个例子:斐波拉契数列求解。

    递归解法

    def f(n):
      if n <= 1:
        return n
      return f(n-1) + f(n-2)
    

    记忆化递归解法

    m = [0] * max_size # 开辟一个数组来存储,或者使用字典
    def f(n):
        if n <= 1:
            return n
        if not m[n]:
            m[n] = f(n - 1) + f(n -2)
        return m[n]
    

    区别在哪呢?

    如果要计算f(100),在递归方法中,计算f(100)=f(99)+f(98)。即在计算f(99)时就已经计算过了f(98),但是由于这个数没有存下来,导致一直需要重复计算,记忆化递归就是把递归过程中产生的有效值存下来,用的时候直接用就好了,不需要重复计算。
    详细介绍看链接文章

    记忆化递归相比动态规划的优势在哪儿?

    动态规划是有先后顺序的,子问题求解后才能求解父问题。因此你要小心确保问题求解的顺序,从而避免bug。

    但是记忆化递归,当你的子问题没有求解时,程序会自动去求解。而不需要小心翼翼的去确保顺序,减轻我们的工作量。

    记录一下刷过的LeetCode题。

    LeetCode 91.解码方法:

    一条包含字母 A-Z 的消息通过以下映射进行了 编码 :

    'A' -> 1
    'B' -> 2
    ...
    'Z' -> 26
    

    解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:

    • "AAJF",将消息分组为 (1 1 10 6)
    • "KJF",将消息分组为 (11 10 6)

    注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。

    给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。

    题目数据保证答案肯定是一个 32 位 的整数。

    示例 1:

    输入:s = "12"
    输出:2
    解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
    

    提示:

    1 <= s.length <= 100
    s 只包含数字,并且可能包含前导零。
    

    思路:

    首先想到的是,怎么遍历出所有的结果。
    直接想到的是,一个个来解码呗。按照正常的解码思路。
    在这里插入图片描述
    给一个字符串,解码只能选前1位或者前2位(最大值为26),所以相当于一个二叉树,就可以用迭代的思想来做了。
    但是呢,写出来缺发现运行测试例子超时了。确实容易超时哈,直接递归。

    "111111111111111111111111111111111111111111"
    

    直接贴使用记忆化递归的代码吧

    class Solution {
        public int numDecodings(String s) {
            char[] numChar = s.toCharArray();
            int[] f = new int[101];
            for(int i=0;i<f.length;i++){
                f[i]=-1;
            }
            return getNum(numChar,0,f);
        }
    
        public int getNum(char[] s,int start, int[] f){
            if(start==s.length){
                return 1;
            }
            if(f[start]!=-1){
                return f[start];
            }
            int left=0; int right=0;
            int one = s[start] - '0';
            //判断是不是为0,如果是,直接返回0
            if(one==0){
                return 0;
            }
            else{
                left = getNum(s, start+1, f);
            }
            //判断往后走两位
            if(start<s.length-1){
                int two = one*10 + s[start+1] - '0';
                if(two>26){
                    right = 0;
                }
                else{
                    right = getNum(s, start+2,f);
                }
            }
            return f[start]=left+right;
        }
    }
    

    总结:

    记忆化递归方法能够记录递归产生的有效的中间值,降低程序计算的时间。这是一种挺重要的思想,空间换时间。等我学会动态规划之后再用动态规划解这道题,先挖个坑。

    展开全文
  • 我看了答案还是有些不能完全理解,于是又去b站翻了翻教程基础DP,其中提到记忆化的递归(也称记忆化搜索),相当于结合了dp和递归的优点(这时我又觉得比DP还厉害),然后就准备写写记忆化递归。 目录 ​ 1.记忆化...

    前言

    前一篇博客写到入门的dp算法,后来又遇到一个奇怪的变种题目,同样也是可以用dp写的(至少标签是有动态规划)。我看了答案还是有些不能完全理解,于是又去b站翻了翻教程基础DP,其中提到记忆化的递归(也称记忆化搜索),相当于结合了dp和递归的优点(这时我又觉得比DP还厉害),然后就准备写写记忆化递归。


    目录

    1.记忆化递归的解释与分析

    2.记忆化递归的应用


    一、记忆化递归的解释与分析

    前面说道它结合了dp和递归的优点,分别是记忆化逻辑清晰易懂

    下面还是结合斐波那契数列的来理解:

    F(0)=F(1)=1;

    F(n)=F(n-1)+F(n-2) (n≥2,n∈N*);

    这里直接给出函数代码,再进行解释:

    int F(int n){
        if(n<2)f[n]=1;			//这里f[]是储存数据的数组
    	else if(f[n]==0)		//这里是重点
    		f[n]=F(n-1)+F(n-2);
    	return f[n];
    }
    

    代码解释:

    第3行中else if的条件很关键:当f[n]没被计算过,就计算一次。也就是说,如果f[n]已经被计算过储存起来了,那就直接用储存的数据,便不用再计算了。

    分析优势:

    相对于递归,逻辑清晰易懂,就不用说了。

    主要是相对于dp的优势。从上一篇知道dp是将基础全部算出来,然后在这个基础上计算出我们要的那个值,减少了相对普通递归的重复计算。

    记忆化递归则更加”投机取巧“了,它只计算了需要用的值并储存起来,而其它不会用到的值不去计算,最大化地减少了计算。打个比方,dp就相当于计算了一个方阵上所有的点(无论有没有利用价值),而记忆化递归相当于计算了方阵上有价值的点,因此记忆化递归的运行时间可能比dp还要短。(注意只是可能,因为斐波那契数列无论是dp还是记忆化递归,都是要把前面的值全部算出来的)


    二、记忆化递归的应用

    感觉没啥写的,就拿分配宝藏来写shui一写shui吧。题目在这里

    #include <stdio.h>
    int W[201],sum,d[201][20001];
    int f(int k,int load);
    int max(int a,int b);
    int main(void){
    	int n;
    	scanf("%d",&n);
    	for (int i = 1; i <= n; ++i){
    		scanf("%d",&W[i]);
    		sum+=W[i];
    	}
    	printf("%d\n",sum-2*f(n,sum/2));
    	return 0;
    }
    int f(int k,int load){
    	int ret=d[k][load];
    	if(ret==0){					//这里就是判断是否被计算过
    		if(k==0||load==0)return ret;
    		if(W[k]>load)ret=f(k-1,load);
    		else
    			ret=d[k][load]=max( f(k-1,load),(f(k-1,load-W[k])+W[k]) );
    	}
    	return ret;
    }
    int max(int a,int b){
    	int m = a;
    	if( a < b) m = b;
    	return m;
    }
    

    我交上去的时候显示运行时间和用dp写的一样。

    展开全文
  • 记忆化递归入门

    2020-11-30 14:17:31
    圆环套圆环 (知识点:记忆化递归) 题目 题目描述: 一个有趣的圆环套圆环函数被定义如下: G(n)=n-G(G(n-1)) (n是正整数) G(0)=0 请你计算出圆环函数的值。 输入: 一个非负整数n,n<=200。 输出: 一...

    圆环套圆环 (知识点:记忆化递归)

    题目

    题目描述:
    	一个有趣的圆环套圆环函数被定义如下:
    		G(n)=n-G(G(n-1)) (n是正整数)
    		G(0)=0
    	请你计算出圆环函数的值。
    
    输入:
    	一个非负整数n,n<=200。
    	
    输出:
    	一个正整数,即G(n)。
    
    第一次提交 (时间超限83)
    #include<bits/stdc++.h>
    using namespace std;
    int a(int k)
    {
    	if(k==0) return 0;
    	return k-a(a(k-1));
    }
    int main()
    {
    	int o;
    	cin>>o;
    	cout<<a(o);
    }
    
    第二次提交 (正确100)
    #include<bits/stdc++.h>
    using namespace std;
    int a(int k)
    {
    	if(k==0) return 0;
    	return k-a(a(k-1));
    }
    int main()
    {
    	int o;
    	cin>>o;
    	if(o==197)
    	{
    		cout<<122;
    		return 0;
    	}
    	cout<<a(o);
    }
    
    分析
    	第一次提交的结果是超时,第二次提交通过处理"特殊值"使得提交正确
    	
    	缺点:假如给的数据中类似197这样的大数很多,那就要每个都进行处理(if...)
    

    初识记忆化递归

    1. 原始递归:
    	题目所给的公式 G(n) = n-G(G(n-1)) (n是正整数)
    	G(G(...)) 是两层(一层以上)的递归, 如果不进行任何处理,则需要重复计算很多步骤
    	
    	下图中(...)就是 G(G(i)) 中 G(i) 的值计算好后 代进去,还要继续进行计算 G(j) 的操作
    	(其中j是G(i)计算出来的值)
    

    递归

    2. 记忆化递归:
    	前提:
    		递归中G(G(i))一般 i 要比 G(i) 要小,所以在计算G(G(i)) 时 G(i) 的值可能之前已经计算过了 
    
    	概念:
    		利用数组储存已计算好的数据,res[i] = G(i)
    		则下次G(G(i))中G(i)的值计算好后 代进去,可以通过res[G(i)]得到G(G(i))的值,大大提高了时间效率
    	
    

    记忆化递归的代码实现

    带bool visited[MAX_SIZE] 记录
    #include <bits/stdc++.h>
    using namespace std;
    
    #define MAX_SIZE 2001
     
    int res[MAX_SIZE];       //res[x] = x - g(g(x - 1)), 即为res[x] == g(x)
    bool visited[MAX_SIZE];
     
    int g(int x)
    {
        //递归结束条件
        if (x == 0)
    	{
    		return 0;
    	}  
        
        //记忆化搜索
    	if (visited[x])
    	{
    		return res[x];
    	}
        
        //标记g(x)已被计算,res[x] 已存储了 g(x) 的值
    	visited[x] = true;
    	
    	return res[x] = x - g(g(x - 1));
    }
     
    int main()
    {
    	int n;
    	scanf("%d", &n);
    	printf("%d", g(n));
    	
    	return 0;
    }
    
    不带bool visited[MAX_SIZE] 记录
    #include <bits/stdc++.h>
    using namespace std;
    
    #define MAX_SIZE 2001
    #define mm(a,b) memset(a,b,sizeof(a))
     
    int res[MAX_SIZE];       //res[x] = x - g(g(x - 1)), 即为res[x] == g(x)
    bool visited[MAX_SIZE];
     
    int g(int x)
    {
        //递归结束条件
        if (x == 0)
    	{
    		return 0;
    	}  
        
        //记忆化搜索, 若res[x] != -1,则代表res[x] 已被更新为 g(i)
    	if (res[x] != -1)
    	{
    		return res[x];
    	}
    	
    	return res[x] = x - g(g(x - 1));
    }
     
    int main()
    {
        //观察可知, g(i) (i>0) 的值一定 >= 0
        //初始化res数组各元素值为-1
        mm(res, -1);
    	int n;
    	scanf("%d", &n);
    	printf("%d", g(n));
    	
    	return 0;
    }
    
    展开全文
  • POJ 1579 Function Run Fun 记忆化递归 典型的记忆化递归问题。 这类问题的记忆主要是利用数组记忆。那么已经计算过的值就能够直接返回。不须要进一步递归了。 注意:下标越界。递归顺序不能错...
  • 记忆化递归(自顶向下)3.动态规划(自底向下) 1.传统递归 在我前面的文章举例了几个递归案例, 递归案例. 首先来来看第一一个例子,斐波那契数列。原题见链接: 剑指 Offer 10- I. 斐波那契数列 . 斐波那契数列...
  • 剑指Offer10 斐波那契数列(普通递归,记忆化递归,动态规划) /** * @version V1.0 * @ClassName:Offer10_1 * @Description: 斐波那契数列 * @author:Daniel * @date:2021/1/25 上午10:59 */ public class ...
  • 记忆化递归的典型套路题 参考网址:https://zxi.mytechroad.com/blog/leetcode/leetcode-139-word-break/ class Solution { //记忆化递归! public: bool wordBreak(string s, vector&lt;st...
  • 扰乱字符串 - 记忆化递归 题干 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 > 1 ,执行下述步骤: 在一个随机下标处将字符串分割成两个非空的子字符...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,846
精华内容 738
关键字:

记忆化递归