廊坊集团网站建设,安装配置wordpress,类似电影天堂的网站 怎么做,企业网站建设项目策划书目录 文章目录 前言 一、记忆化搜索 二、题目概略 三、斐波拉契数 四、Function 五、天下第一 六、滑雪 总结 亲爱的读者朋友们#xff0c;大家好啊#xff01;不同的时间#xff0c;相同的地点#xff0c;今天又带来了关于搜索部分的讲解。接下来我将接着我前面文章的内容… 目录 文章目录 前言 一、记忆化搜索 二、题目概略 三、斐波拉契数 四、Function 五、天下第一 六、滑雪 总结 亲爱的读者朋友们大家好啊不同的时间相同的地点今天又带来了关于搜索部分的讲解。接下来我将接着我前面文章的内容开始讲解以下记忆化搜索的部分了。 lets go! 前言
前面我们讲解了剪枝的内容我们接着它继续剪枝。
记忆化搜索就是我们剪枝的一大部分我们接下来就学习我们的记忆化搜索吧 一、记忆化搜索
记忆化搜索也是一种剪枝的策略
通过⼀个备忘录记录第⼀次搜索到的结果当下⼀次搜索到这个状态时直接在备忘录⾥⾯找结果。
我们接下来就看看这部分的题目在题目中来理解记忆化搜索吧
二、题目概略
509. 斐波那契数 - 力扣LeetCode
P1464 Function - 洛谷
P5635 【CSGRound1】天下第一 - 洛谷
P1434 [SHOI2002] 滑雪 - 洛谷
三、斐波拉契数 我们看完题目后会发现很简单一个简单的递归就可以解决了所以我们很快就可以写出这道题 但是我们执行时间怎么这么多
如果卡时间我们不就过不了了吗所以该怎么办
我们画一下对应的决策树 我们发现在递归的过程中会出现很多重复的展开我们就需要去将这些重复的内容全部去掉才对。这时候我们记忆化搜索就可以来帮助我们了
我们可以将对应的递归结果存下来如果再次需要去递归这个数那么我们判断一下直接拿对应的值即可
可以看一下它的数据范围是小于等于30所以我们创建一个35大小的数组即可
int f[35];//备忘录存放对应下标i的斐波拉契值 这样我们就大幅度的降低了我们的时间消耗。记忆化搜索就帮我们剪掉对应的那些重复枝丫。
四、Function 首先先理解一下这个题目
我们无非就是要设计一个递归函数从之前的学习后写一个递归函数难度肯定不大。
但是题目后面又说如果出现如w(15, 15, 15)的时候会出现很多的调用这个时候我们就得需要记忆化搜索来记录它的结果剪掉多余的枝丫。
我们来实现一下最简单的版本
#include iostream
using namespace std;
typedef long long LL;
LL a, b, c;
LL dfs(LL a, LL b, LL c)
{if (a 0 || b 0 || c 0) return 1;if (a 20 || b 20 || c 20) return dfs(20, 20, 20);if (a b b c){return dfs(a, b, c - 1) dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);}else {return dfs(a - 1, b, c) dfs(a - 1, b - 1, c) dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);}
}
int main()
{while(cin a b c){if (a -1 b - 1 c -1) break;printf(w(%lld, %lld, %lld) %lld\n, a, b, c, dfs(a, b, c));}return 0;
}
这是没有记忆化搜索的版本我们看看能不能通过呢 会发现全部都超时了所以我们的记忆化搜索是必须要增加上去的
由于这里有三个数我们要通过三个数来映射对应的值所以我们要使用一个三维数组去映射
#include iostream
using namespace std;
typedef long long LL;
const int N 25;
LL f[N][N][N];
LL a, b, c;
LL dfs(LL a, LL b, LL c)
{if (a 0 || b 0 || c 0) return 1;if (a 20 || b 20 || c 20) return dfs(20, 20, 20);if (f[a][b][c]) return f[a][b][c];//查找备忘录 if (a b b c){return f[a][b][c] dfs(a, b, c - 1) dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);}else {return f[a][b][c] dfs(a - 1, b, c) dfs(a - 1, b - 1, c) dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);}
}
int main()
{while(cin a b c){if (a -1 b - 1 c -1) break;printf(w(%lld, %lld, %lld) %lld\n, a, b, c, dfs(a, b, c));}return 0;
} 我们这样就通过了
可能会有读者问为什么多组测试数据不清理数组呢
那是因为我们后面也会用到这个备忘录并不需要清理
五、天下第一 讲这道题的时候我需要先讲一下取模运算的一些内容
对于取模的加法和乘法的性质
(a b c) % p (a % p b % p c % p) % p
(a * b * c) % p (a % p * b % p * c % p) % p
在加法和乘法中括号里面那一坨可以随便加%p并不会影响结果
那么现在再来理解一下这道题吧
我们会有一个x和一个y进行不停的执行取模谁先到0谁就赢
都不能到0就平局
题目很简单只需要通过递归去解决这个相同子问题即可
还有就是每次x和y都会更新x (x y) % p, y ((x y) % p y) % p (x y y) % p
在不停的模中就会出现重复的情况我们就需要记录下对应的结果
#include iostream
using namespace std;
const int N 1e4 10;
char f[N][N];
int T, p;
char dfs(int x, int y)
{if (f[x][y]) return f[x][y];f[x][y] 3;if (x 0) return f[x][y] 1;else if (y 0) return f[x][y] 2;return f[x][y] dfs((x y) % p, (x y y) % p);
}
int main()
{cin T p;while(T--){int x, y;cin x y;char ret dfs(x, y);if (ret 1) cout 1 endl;else if (ret 2) cout 2 endl;else cout error endl;}return 0;
}
我们由于有x和y就采用一个二维数组来映射即可
因为有三种结果我们就不能直接使用bool数组来标记了我们可以使用int或者char去记录
但是int没必要有些浪费空间了我们直接使用char数组去记录即可。
我们一旦进入函数就要给它先打上平局的3才行如果x或者y成了0就修改为对应的1或者2
如果没有最后返回的便是平局 六、滑雪 这道题跟前面几道题的难度就不一样了
我们最简单的方法就是枚举i,j
从i, j位置向四个方向去走将最长的路径找出来
dfs(i, j)返回这个点能滑的最远距离
那么怎么让这个往四个方向去走呢看过前面章节内容的读者就知道这时候我们就需要方向数组dx[]和dy[]去更新我们的x和y了
我们先将最简单代码来写一下 #include iostream
using namespace std;
const int N 110;
int a[N][N];
int r, c;
int dx[] {1, -1, 0, 0};
int dy[] {0, 0, 1, -1};
int dfs(int i, int j)
{int len 1;for (int k 0; k 4; k){int x i dx[k];int y j dy[k];if (x 1 x r y 1 y c a[x][y] a[i][j]){len max(len, dfs(x, y) 1);}}return len;
}int main()
{cin r c;for (int i 1; i r; i){for (int j 1; j c; j){cin a[i][j];}}int ret 1;for (int i 1; i r; i){for (int j 1; j c; j){ret max(ret, dfs(i, j));}}cout ret endl;return 0;
} 我们会发现还是有个例子超时了我们不加记忆化搜索还是过不了。
由于每次去遍历的时候都会遍历到很多之前走过的节点我们去遍历的话就会浪费很多时间
我们就得想办法将每个访问过的点记忆下来这样再访问这个点就可以直接拿到对应的值了。 #include iostream
using namespace std;
const int N 110;
int a[N][N];
int r, c;
int dx[] {1, -1, 0, 0};
int dy[] {0, 0, 1, -1};
int f[N][N];
int dfs(int i, int j)
{if(f[i][j]) return f[i][j];int len 1;for (int k 0; k 4; k){int x i dx[k];int y j dy[k];if (x 1 x r y 1 y c a[x][y] a[i][j]){len max(len, dfs(x, y) 1);}}return f[i][j] len;
}int main()
{cin r c;for (int i 1; i r; i){for (int j 1; j c; j){cin a[i][j];}}int ret 1;for (int i 1; i r; i){for (int j 1; j c; j){ret max(ret, dfs(i, j));}}cout ret endl;return 0;
}我们发现这道题难度不大只要通过深度搜索我们就可以很简单的将对应的代码写出来。
通过添加映射的备忘录将值记录即可。
但是要注意的是一定是要出现大量的相同的情况我们才去使用备忘录记忆化搜索。
如上这样会访问到很多相同节点一般。
我们就要去使用记忆化搜索剪枝 总结
亲爱的读者朋友们这篇文章希望大家能够看完前面的文章再来读这样的话会更加得心应手。
希望大家多多点赞 收藏 关注
