记忆化搜索专题——算法简介&力扣实战应用

举个例子，当我们使用普通的暴搜递归法求斐波那契数时，意味着每个节点都需要遍历一遍，时间复杂度为O(2^N)，但是这其中出现大量完全重复的递归树，大量重复的递归导致时间效率严重降低。这时，我们就可以使用一个“备忘录”所出现过的数据存起来，递归时若遇见重复的问题时，直接从“备忘录”中取值即可，不必再次重复递归。这样一来，我们可将时间复杂优化为线性级别：O(N)。

我们以添加“备忘录”的形式，将数据记忆起来，减少大量重复的递归，这样的暴搜优化( O(2^N) --> O(N) )算法就称为记忆化搜索。

注意：

并非所有的递归暴搜都可改为记忆化搜索，只有在递归的过程中，出现了大量完全相同的问题时（并非相同子问题），才可以使用记忆化搜索进行优化。

1.2 如何实现记忆化搜索

添加备忘录 ---> <可变参数，返回值>
每次进入递归的时候，瞅一瞅备忘录里面是否已存在想要的结果
每次递归返回的时候，将结果放到备忘录中存起来

1.3 记忆化搜索与动态规划的区别

其实记忆化搜索与动态规划本质上都是一回事。

都属于暴力解法(暴搜)
都是对暴搜的优化：把计算过的值，存起来

但是不同的是：

记忆化搜索是以递归的形式进行的
动态规划是以递推(循环)的形式进行的
记忆化搜索是自顶向下（dfs(n) --> dfs(n-1) 、 dfs(n-2)）
动态规划是自底向上（dp[1] 、 dp[2] --> dp[3] ）

2、算法应用【leetcode】

2.1 题一：斐波那契数

. - 力扣（LeetCode）

相信对于斐波那契数的计算，大家都已了然于心，这里就不多废话了，只向大家展示三中不同解法：

递归暴搜解法：O(2^N)
记忆化搜索解法(暴搜优化)：O(N)
动态规划解法(暴搜优化)：O(N)

2.1.1 递归暴搜解法代码

class Solution {
    public int fib(int n) {
        return dfs(n);
    }
    public int dfs(int n) {
        if(n == 0 || n == 1) return n;
        return dfs(n - 1) + dfs(n - 2);
    }
}

2.1.2 记忆化搜索解法代码

class Solution {
    //记忆化搜索
    int[] memo;//memory
    public int fib(int n) {
        memo = new int[31];
        Arrays.fill(memo, -1);//初始化时，填入不可能出现的值
        return dfs(n);
    }
    public int dfs(int n) {
        if(memo[n] != -1) return memo[n];
        if(n == 0 || n == 1) {
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
}

2.1.3 动态规划解法代码

class Solution {
    //动态规划
    int[] dp;
    public int fib(int n) {
        dp = new int[31];
        dp[0] = 0; dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

2.2 题二：不同路径

. - 力扣（LeetCode）

2.2.1 算法原理

经过分析，可以发现：到达(x,y)位置的路径数=到达(x,y-1)的路径数+到达(x-1,y)的路径数

设计递归函数体：dfs(m,n) = dfs(m,n-1)+dfs(m-1,n)

函数出口：

if(m == 0 || n == 0) return 0;（从下标1开始为有效位置）
if(m== 1&&n ==1) return 1;//特殊处理

经过验证，纯暴搜解法是会超时的，经分析，问题中出现了大量重复的问题，采取记忆化搜索算法和动态规划进行优化。

2.2.2 记忆化搜索代码

class Solution {
    //记忆化搜索
    int[][] memo;
    public int uniquePaths(int m, int n) {
        //从下标1,1开始
        memo = new int[m + 1][n + 1];
        return dfs(m, n);
    }
    public int dfs(int m, int n) {
        if(memo[m][n] != 0) return memo[m][n];
        if(m == 0 || n == 0) {
            return 0;
        }
        if(m == 1 && n == 1) {
            memo[m][n] = 1;
            return 1;
        }
        memo[m][n] =  dfs(m, n - 1) + dfs(m - 1, n);
        return memo[m][n];
    }
}

2.2.3 动态规划代码

class Solution {
    public int uniquePaths(int m, int n) {
        //动态规划
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1;j < n + 1; j++) {
                if(i == 1 && j == 1) continue;
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
}

2.3 题三：最长递增子序列

2.3.1 算法原理

因为是最长递增子序列，所以只能从当前位置向后找。

函数头：dfs(pos)；//pos位置处的最长子序列
从当前位置pos开始，选出后面位置中最长的子序列len(注意：要求nums[i] > nums[pos])，再得len+1(当加上前位置)，就是当前位置的最长子序列。

2.3.2 记忆化搜索代码

class Solution {
    //记忆化搜索
    int n;
    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        n = nums.length;
        int[] memo = new int[n];
        for(int i = 0; i < n; i++) {
            ret = Math.max(ret, dfs(nums, i, memo));
        }
        return ret;
    }
    public int dfs(int[] nums, int pos, int[] memo) {
        if(memo[pos] != 0) return memo[pos];
        int ret = 1;
        for(int i = pos + 1; i < n; i++) {
            if(nums[i] > nums[pos]) {
                ret = Math.max(ret,  dfs(nums, i, memo) + 1);
            }
        }
        memo[pos] = ret;
        return ret;
    }
}

2.3.3 动态规划代码

class Solution {
    //动态规划
    int n;
    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i + 1; j < n; j++) {
                if(nums[i] < nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(dp[i], ret);
        }
        return ret;
    }
}

2.4 题四：猜数字大小II

. - 力扣（LeetCode）

2.4.1 算法原理

暴力枚举出所有可能出现的情况，选出花费最小的最佳策略。

每一种情况都需要选出左右子树中话费金额的最大值(保证能赢)
每种情况话费的金额为：max(左，右)+本身
选出所有情况中花费最小的最佳策略。

2.4.2 算法代码

class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return dfs(1, n);
    }
    public int dfs(int s, int e) {
        int ret = Integer.MAX_VALUE;
        if(s >= e) {
            return 0;
        }
        if(memo[s][e] != 0) return memo[s][e];
        for(int i = s; i <= e; i++) {
            int left = dfs(s, i - 1);
            int right = dfs(i + 1, e);
            ret = Math.min(Math.max(left, right) + i, ret);
        }
        memo[s][e] = ret;
        return ret;
    }
}

2.5 题五：矩阵中的最长递增路径【困难】

. - 力扣（LeetCode）

2.5.1 算法原理

枚举所有节点，选出所有节点中最长的路径
函数设计：dfs(i,j) --> 返回(i,j)位置的最长路径
一个位置的最长路径是固定的 --> 备忘录int[][] memo

2.5.2 算法代码

class Solution {
    int m, n;
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int[][] matrix;
    int[][] memo;//备忘录
    public int longestIncreasingPath(int[][] matrix_) {
        matrix = matrix_;
        m = matrix.length; n = matrix[0].length;
        memo = new int[m + 1][n + 1];
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                ret = Math.max(ret, dfs(i, j));
            }
        }
        return ret;
    }
    public int dfs(int i, int j) {
        if(memo[i][j] != 0) return memo[i][j];
        int ret = 1;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                //求出当前位置的最长路径
                ret = Math.max(ret, dfs(x, y) + 1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
}

END

原文地址：https://blog.csdn.net/2401_83595513/article/details/142311770

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：70. 爬楼梯
下一篇：强化学习Reinforcement Learning|Q-Learning|SARSA|DQN以及改进算法

PostgreSQL运用关键点是什么呢？
存储过程和函数：PostgreSQL支持存储过程和函数，允许将一组SQL语句封装起来作为一个独立的单元执行。创建表：使用CREATE TABLE语句可以创建一个新表，并定义其列（字段）和数据类型。创建
阅读更多2024-09-21
UI自动化测试框架搭建详解
通过上面几步一个模块的ui测试流程基本讲解完成，这个框架的目的就是便于维护，里面也可以添加 api 及数据源的操作，数据库的关联等，还有另外一种方法 maven，在pom 里配置相关的testng
阅读更多2024-09-21
C++之spring
不是最后一个数据运行结果如下：可能string这里会显得迭代器有点繁琐，但是它是适用于所有容器通用的方法，下标+[]只适用于string,vector这样的底层是连续的物理结构，但是像链表就不太适合，
阅读更多2024-09-21
如何设计出一个比较全面的测试用例
在基于需求进行测试用例设计时，我们需要从功能需求和非功能需求两个方面进行全面的分析。通过明确测试目标、识别关键功能点、设计测试场景和编写测试用例等步骤，可以确保软件的质量满足需求文档中的要求。同时，我
阅读更多2024-09-21
[SAP ABAP] 创建数据元素
本文主要讲解SAP ABAP中的创建数据元素相关知识点
阅读更多2024-09-21
IDEA中实现springboot热部署
IDEA中实现springboot热部署
阅读更多2024-09-21
docker操作的基本命令加容器的基本命令（仅供自己参考）
容器内的数据可以到数据卷当中，数据卷中的数据也能到容器，这个交换是实时的）宿主机的目录挂载：这个挂载就是不在默认的数据卷存放路径了（/var/lib/docker/volumes/），这个路径可以是随
阅读更多2024-09-21
中国电子学会202403青少年软件编程（Python）等级考试试卷（四级）真题
6. 一个荷花池,第一天荷花开放得很少,第二天开放的数量是第一天的两倍, 之后的每一天,荷花都会以前一天两倍的数量开放。36. 数的分解给出一个正整数a,要求分解成若干个正整数的乘积,即 a = a1
阅读更多2024-09-21
C++/Qt 集成 AutoHotkey
上一篇介绍了AutoHotkey的基本情况和使用，其功能丰富易用，于是搬出我们的老朋友 C++/Qt，将AutoHotkey 集成到 C++/Qt开发环境，使其为我们所用。C++ AutoHotkey
阅读更多2024-09-21
计算机毕业设计之：基于微信小程序的校园流浪猫收养系统
博主介绍： ✌我是阿龙，一名专注于Java技术领域的程序员，全网拥有10W+粉丝。作为CSDN特邀作者、博客专家、新星计划导师，我在计算机毕业设计开发方面积累了丰富的经验。同时，我也是掘金、华为云、
阅读更多2024-09-21

记忆化搜索专题——算法简介&力扣实战应用

1、记忆化搜索算法简介

1.1 什么是记忆化搜索

1.2 如何实现记忆化搜索

1.3 记忆化搜索与动态规划的区别

2、算法应用【leetcode】

2.1 题一：斐波那契数

2.1.1 递归暴搜解法代码

2.1.2 记忆化搜索解法代码

2.1.3 动态规划解法代码

2.2 题二：不同路径

2.2.1 算法原理

2.2.2 记忆化搜索代码

2.2.3 动态规划代码

2.3 题三：最长递增子序列

2.3.1 算法原理

2.3.2 记忆化搜索代码

2.3.3 动态规划代码

2.4 题四：猜数字大小II

2.4.1 算法原理

2.4.2 算法代码

2.5 题五：矩阵中的最长递增路径【困难】

2.5.1 算法原理

2.5.2 算法代码

相关文章