DFS:记忆化搜索

这篇具有很好参考价值的文章主要介绍了DFS:记忆化搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

​​​​​​​

一、记忆化搜索vs动态规划

. - 力扣(LeetCode)

DFS:记忆化搜索,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    //记忆化搜索
    //1、设置一个备忘录,要确保备忘录初始化的结果不能跟我们实际计算的结果相同
    //2、添加备忘录,计算的时候,如果备忘录的位置是初始值,进行修改
    //3、每次计算的时候,去备忘录瞅一瞅,找到的话,就可以不算了
    int memory[31];
    int fib(int n) 
    {
      memset(memory,-1,sizeof(memory));//利用memset进行初始化成-1
      return dfs(n);
    }

    int dfs(int n)
    {
        //递归进入前,去备忘录瞅瞅
        if(memory[n]!=-1) return memory[n];
        if(n==0||n==1) 
        {
            memory[n]=n;
            return memory[n];
        }
        else 
        {
            memory[n]=dfs(n-1)+dfs(n-2);
            return memory[n];
        }
    }
};

二、不同路径

DFS:记忆化搜索,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    int uniquePaths(int m, int n)
    {
        //记忆化搜索
        vector<vector<int>> memo(m+1,vector<int>(n+1,-1));//建立一个记忆数组
        return dfs(m,n,memo);//dfs去帮我搜索
    }

    int dfs(int i,int j,vector<vector<int>>&memo)
    {
       if(memo[i][j]!=-1) return memo[i][j];
       if(i==0||j==0) return 0;
       if(i==1&&j==1) return 1;
       
        memo[i][j]=dfs(i-1,j,memo)+dfs(i,j-1,memo);
        return memo[i][j];
    }
};

三、最长的递增子序列

DFS:记忆化搜索,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    //记忆化搜索
    //不用记忆化搜索的话会超时,因为本身就是一个多叉树
    int lengthOfLIS(vector<int>& nums) 
    {
       vector<int> memo(nums.size()+1,-1);
       int ret=1;
       for(int i=0;i<nums.size();++i)
       {
          ret=max(dfs(nums,i,memo),ret);
       } 
       return ret;
    }

    int dfs(vector<int>& nums,int pos,vector<int>&memo)//从pos位置开始,以pos位置做起点,往后搜索出他的最长子序列
    {
    //接下去开始从下一个位置开始找
    if(memo[pos]!=-1) return memo[pos];
    int ret=1;
    for(int i=pos+1;i<nums.size();++i)
      {
        if(nums[i]>nums[pos]) //找到了,就更新ret,然后去以下一个位置为起点接着找
        {
           ret=max(ret,dfs(nums,i,memo)+1);
        }
      }
      memo[pos]=ret;
      return memo[pos];
    }
};

四、猜数字大小II

DFS:记忆化搜索,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    int getMoneyAmount(int n) 
    {
    vector<vector<int>> memo(n+1,vector<int>(n+1));
      return dfs(1,n,memo);
    }

    int dfs(int left,int right, vector<vector<int>>&memo)
    {
        if(left>=right) return 0;
        if(memo[left][right]) return memo[left][right];//去备忘录瞅瞅 
        int ret=INT_MAX;
        for(int i=left;i<=right;++i)
        {
            int l=dfs(left,i-1,memo);//左边的最小
            int r=dfs(i+1,right,memo);//右边的最小
            ret=min(ret,max(l,r)+i);
        }
        memo[left][right]=ret;
        return memo[left][right];
    }
};

五、矩阵的最长递增路径

DFS:记忆化搜索,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int m,n;
    //记忆化搜索,不然会超时
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        int ret=1;
        m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> memo(m+1,vector<int>(n+1));
       for(int i=0;i<m;++i)
       for(int j=0;j<n;++j)
         {
           ret=max(ret,dfs(matrix,i,j,memo));//以任意坐标为起点,dfs去帮我们找到最大的路径
         }
         return ret;
    }
    int dfs(vector<vector<int>>& matrix,int i,int j, vector<vector<int>>&memo)
    {
        if(memo[i][j]!=0) return memo[i][j];
       int ret=1;
       for(int k=0;k<4;++k)
       {
         int x=i+dx[k],y=j+dy[k];
         if(x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]) 
             ret=max(dfs(matrix,x,y,memo)+1,ret);
       }
       memo[i][j]=ret;//填备忘录
       return memo[i][j];
    }
};

DFS:记忆化搜索,递归、搜索与回溯算法总结,深度优先,算法,leetcode,笔记,c++文章来源地址https://www.toymoban.com/news/detail-845353.html

到了这里,关于DFS:记忆化搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(53)
  • DFS(基础,回溯,剪枝,记忆化)搜索

    DFS(深度优先搜索) 基于递归求解问题,而针对搜索的过程 对于问题的介入状态叫初始状态,要求的状态叫目标状态 这里的搜索就是对实时产生的状态进行分析检测,直到得到一个目标状态或符合要求的最佳状态为止。对于实时产生新的状态的过程叫扩展 搜索的要点: 1.选定初

    2024年04月12日
    浏览(37)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(63)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(51)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(52)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(51)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(78)
  • 如何实现一个简单的深度优先搜索(DFS)算法?

    前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发者,这里都将为你提供一

    2024年02月07日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包