算法:记忆化搜索「建议收藏」

算法:记忆化搜索「建议收藏」概述记忆化搜索是一种典型的空间换时间的思想。记忆化搜索的典型应用场景是可能经过不同路径转移到相同状态的dfs问题。更明确地说,当我们需要在有层次结构的图(不是树,即当前层的不同节点可能转移到下一层的相同节点)中自上而下地进行dfs搜索时,大概率我们都可以通过记忆化搜索的技巧降低时间复杂度。例子:青蛙过河题目描述一只青蛙想要过河。假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。青蛙可以跳上石子,但是不可以跳入水中。给你石子的位置列表stones(用单

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

概述

记忆化搜索是一种典型的空间换时间的思想。
记忆化搜索的典型应用场景是可能经过不同路径转移到相同状态dfs问题
更明确地说,当我们需要在有层次结构的(不是树,即当前层的不同节点可能转移到下一层的相同节点)中自上而下地进行dfs搜索时,大概率我们都可以通过记忆化搜索的技巧降低时间复杂度。

例子:青蛙过河

题目描述

一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。

给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。

开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。

如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k – 1、k 或 k + 1 个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。

示例1

输入:stones = [0,1,3,5,6,8,12,17]
输出:true
解释:青蛙可以成功过河,按照如下方案跳跃:跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。

示例2

输入:stones = [0,1,2,3,4,8,9,11]
输出:false
解释:这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。

分析

对于我构造的示例 stones = [0,1,3,4,5,6,7,10,15],搜索路径如下:
在这里插入图片描述
可以看到从状态[5,1]和状态[5,2]都能转移到状态[7,2]而[7,2]这个状态并不能转移到终点这个结论是可以被存储起来的,避免对同一个结论的重复计算。

就好比很多人走迷宫,前人走到[7,2]发现没有路能走出去(无法转移到目标状态),他回到这个节点(回溯)时在此立下告示牌(记忆化标签),告诉后人不要来这个地方,来了也是白来,后人看到告示牌自然就去尝试其他可能能走出去的路即可(转移到没有打上记忆化标签的状态)。前人栽树后人乘凉。

代码

/* 细节:dfs中的参数pos不是位置,而是位置在数组中的下标。这样便于在vector中记录。 */

class Solution { 
   
public:
    vector<unordered_map<int, bool>> flag;

    
    bool dfs(int pos, int preJump, vector<int>& stones) { 
   
        if(pos == stones.size()-1) return true;
        if (flag[pos].count(preJump)) { 
   
            return false;
        }

        for(int jump = preJump-1; jump<=preJump+1; jump++) { 
   
            if(jump<=0) continue;
            int nextpos = lower_bound(stones.begin(), stones.end(), stones[pos]+jump) - stones.begin();
            if(nextpos != stones.size() && stones[nextpos] == stones[pos]+jump && dfs(nextpos, jump, stones)) { 
   
                return true;
            }
        }

        return flag[pos][preJump] = false;
    }

    bool canCross(vector<int>& stones) { 
   
        int n = stones.size();
        flag.resize(n);
        return dfs(0, 0, stones);
    }
};

在学习算法的初期,最需要锻炼的就是对症下药的能力。下面来看一道典型不能使用记忆化搜索的反例:

反例:停在原地的方案数

题目描述

有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。

每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。

给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。

由于答案可能会很大,请返回方案数 10^9 + 7 后的结果。

示例1

输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动

示例2

输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动

分析

如图所示,图中每个节点S值表示当前还剩多少步要走,pos值表示当前处在的位置。每个节点对应一个方案数,我们要计算的是根节点(S=3,pos=0)的方案数。
在这里插入图片描述
乍一看本题也是自上而下在有层次结构的图中搜索,且也符合当前层的不同节点都转移到下一层的同一节点。但问题在于本题并不是dfs过程,因为要想知道(S=2,pos=1)节点的值,需要同时知道(S=1,pos=0)、(S=1,pos=1)、(S=1,pos=2)这三个节点的值。其实对于计算方案数的问题,最先想到的方法应该是动态规划。事实证明这道题的确用动态规划是最好的解法。

动态规划之所以能比递归快很多,就是通过将重复子问题的解存储起来,重复子问题的解只需算一次即可,不必重复计算,自底向上一步步得到原问题的解。从这个角度来说,动态规划和记忆化搜索的共同点在于都是空间换时间的思想。

回到本题的dp解法:

dp定义:dp[i][j] 表示还可以走i步时,位于位置j的方案数
初始化:dp[0][0] = 1
待求结果:dp[steps][0]
状态转移方程:dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]

代码

class Solution { 
   
public:
    int numWays(int steps, int arrLen) { 
   
        // dp[i][j] 表示还剩i个step时位于位置j的方案数。要求dp[steps][0]
        // 由于steps步后,位置最远走到steps,因此列数应该是min(steps+1,arrLen)
        int col = min(steps+1, arrLen);
        vector<vector<int>> dp(steps+1,vector<int>(col, 0));  
        // init
        dp[0][0] = 1;
        int mod = 1000000000+7;
        for(int i=1;i<=steps;i++) { 
   
            for(int j=0;j<col;j++) { 
   
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
                if(j-1>=0) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
                if(j+1<col) dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod;
                if(i==steps && j==0) break;
            }
        }
        return dp[steps][0];
    }
};

滚动数组优化:



class Solution { 
   
public:
    int numWays(int steps, int arrLen) { 
   
        // 由于steps步后位置最远走到steps,因此列数可以优化为min(steps+1,arrLen)。可以大大降低空间和时间复杂度
        // 由于转移到dp[i]只需要dp[i-1],因此使用滚动数组,可以将dp数组的行数优化为2。
        int col = min(steps+1, arrLen);
        vector<vector<int>> dp(2,vector<int>(col, 0));  
        // init
        dp[0][0] = 1;
        int mod = 1000000000+7;
        for(int i=1;i<=steps;i++) { 
   
            for(int j=0;j<col;j++) { 
   
                int dst = i%2, src = 1 - i%2 ;  // i为奇数时从[0]转移到[1],反之亦然
                dp[dst][j] = 0;  // 不要忘记将待填充的dp初值设为0,因为里面保存这之前的数据
                dp[dst][j] = (dp[dst][j] + dp[src][j]) % mod;
                if(j-1>=0) dp[dst][j] = (dp[dst][j] + dp[src][j-1]) % mod;
                if(j+1<col) dp[dst][j] = (dp[dst][j] + dp[src][j+1]) % mod;
                if(i==steps && j==0) break;
            }
        }
        
        if(steps % 2) return dp[1][0];
        return dp[0][0];
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164442.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 超分辨率重建总结(超分辨率重建算法程序)

    1.SRCNN:—2,3改进开山之作,三个卷积层,输入图像是低分辨率图像经过双三次(bicubic)插值和高分辨率一个尺寸后输入CNN。图像块的提取和特征表示,特征非线性映射和最终的重建。使用均方误差(MSE)作为损失函数。2.FSRCNN特征提取:低分辨率图像,选取的核9×9设置为5×5。收缩:1×1的卷积核进行降维。非线性映射:用两个串联的3×3的卷积核可以替代一个5×5…

  • Protel99SE快捷键大全

    Protel99SE快捷键大全protel99se快捷键enter——选取或启动esc——放弃或取消f1——启动在线帮助窗口tab——启动浮动图件的属性窗口pgup——放大窗口显示比例pgdn——缩小窗口显示比例end——刷新屏幕del——删除点取的元件(1个)ctrl+del——删除选取的元件(2个或2个以上)x+a——取消所有被选取图件的选取状态x——将浮动图件左右翻转y——将浮动图件上下翻转space——将浮动图件旋转90度crtl+ins——将选取图件复制到编辑区里shift+ins——将剪贴板里的

  • ATECC508A芯片开发笔记(一):初识加密芯片

    ATECC508A芯片开发笔记(一):初识加密芯片近年来,随着黑客网络攻击事件频繁发生,网络安全问题亟待解决,同时security方面的软件解决方案也正快速更迭,相关软件开发人员也变得更紧缺。使用传统纯软件的方法实现网络安全加解密、身份认证等算法存在较多缺陷,如执行各类算法的时间、资源消耗较大,并且无法实现密钥等secret的安全存储,这时各类芯片厂商推出了硬件加密芯片来解决上述问题,在增加系统安全性的同时,也极大提高了软件效率。因此针…

  • mysql将字符转换成数字

    mysql将字符转换成数字在操作mysql时,经常需要将字符转换成数字,这一步虽然简单,但不常用的话也很容易忘记,现将在网上找到的方法记录如下:1.将字符的数字转成数字,比如’0’转成0可以直接用加法来实现例如:将pony表中的d进行排序,可d的定义为varchar,可以这样解决select*fromponyorderby(d+0)2.在进行ifnull处理时,比如ifnull(a/b,’0

  • python进阶(6)深拷贝和浅拷贝[通俗易懂]

    python进阶(6)深拷贝和浅拷贝[通俗易懂]深拷贝和浅拷贝不管对于浅拷贝、还是深拷贝,针对不可变对象str、int、tuple(有点特殊)、boolean,它的内存地址是不变的,拷贝的仅仅是值importcopya=1b=co

  • 树莓派介绍以及FAQ【这是我见过最全的树莓派教程】

    树莓派介绍以及FAQ【这是我见过最全的树莓派教程】一、树莓派简介树莓派是什么?树莓派(RaspberryPi)是尺寸仅有信用卡大小的一个小型电脑,您可以将树莓派连接电视、显示器、键盘鼠标等设备使用。树莓派能替代日常桌面计算机的多种用途,包括文字处理、电子表格、媒体中心甚至是游戏。并且树莓派还可以播放高至4K的高清视频。我们希望将树莓派推广给全世界的青少年电脑爱好者,用于培养计算机程序设计的兴趣和能力。树莓派各版本发布时间和差异对照?二、购买与配送在哪里购买?(说人话京东和淘宝都可以直接购买)树莓派基金会与E络盟与…

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号