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

算法:记忆化搜索「建议收藏」概述记忆化搜索是一种典型的空间换时间的思想。记忆化搜索的典型应用场景是可能经过不同路径转移到相同状态的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)
blank

相关推荐

  • 多边形内有2枚钉子的图形_当多边形内没有钉子

    多边形内有2枚钉子的图形_当多边形内没有钉子Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)Total Submission(s) : 24 Accepted Submission(s) : 7Problem DescriptionStatement of the Problem Several drawing applications allow us to draw polygons and almost all of the

  • 浮动广告代码

    浮动广告代码整个页面的代码如下:<%@PageLanguage=’vb’AutoEventWireup=’false’Codebehind=’floatadv.aspx.vb’Inherits=’

  • Java 编译时多态和运行时多态

    Java 编译时多态和运行时多态根据何时确定执行多态方法中的哪一个,多态分为两种情况:编译时多态和运行时多态。如果在编译时能够确定执行多态方法中的哪一个,称为编译时多态,否则称为运行时多态。一、编译时多态    方法重载都是编译时多态。根据实际参数的数据类型、个数和次序,Java在编译时能够确定执行重载方法中的哪一个。    方法覆盖表现出两种多态性,当对象引用本类实例时,为编译时多态,否则

  • python menuconfig_make menuconfig详解

    python menuconfig_make menuconfig详解makemenuconfig图形化的内核配置makemrproper—–删除不必要的文件和目录.1#makeconfig(基于文本的最为传统的配置界面,不推荐使用)2#makemenuconfig(基于文本选单的配置界面,字符终端下推荐使用)注意:使用makemenuconfig需要安装ncurses(sudoapt-getinstallncurses-dev…

  • 宽度学习(Broad Learning System)

    宽度学习(Broad Learning System)宽度学习系统(BLS)一词的提出源于澳门大学科技学院院长陈俊龙于2018年1月发表的《BroadLearningSystem:AnEffectiveandEfficientIncrementalLearningSystemWithouttheNeedforDeepArchitecture》

  • vue通信、传值的多种方式(详细)

    vue通信、传值的多种方式(详细)Vue通信、传值的多种方式,详解(都是干货):一、通过路由带参数进行传值①两个组件A和B,A组件通过query把orderId传递给B组件(触发事件可以是点击事件、钩子函数等)this.$router.push({path:’/conponentsB’,query:{orderId:123}})//跳转到B②在B组件中获取A组件传递过来的参数…

发表回复

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

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