大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...