记忆化搜索
有小伙伴说想看,于是更新一下。
何为记忆化搜索
我们要先从搜索说起。
搜索,是一个很不错的算法。
优点不少,缺点也不少。
优点没得好说:
骗分水题- 短!
- 好用
- 好调
缺点显而易见,那就是:
TLE的痛
怎么办呢?
这时候就要请出我们的记忆化搜索了。
记忆化 = 搜索 + dp
dp
有个弱点,那就是太难想了。
but,dp
很快,因为要啥有啥。
分析问题看本质,要啥有啥的本质就是有一个数组充当工具人记录答案。
于是我们可以抄袭借鉴一下,把这个思路搬运到搜索里。
搬运三步走:
step1:建好数组
搜索的答案有的时候为$0$,所以直接初始化$-1$就行了。
int f[N][N];
memset(f, -1, sizeof f);
step2:暴力搜索
这个没啥好说,看题写题,把最暴力的算法打上。
小建议:
在抄袭借鉴dp
数组之前,各位大佬可以先把玄学剪枝儿加上。
step3:强行搬运
直接在搜索中加上如下的代码:
int dfs(/*bla bla bla*/int u)//这里只是举一个栗子
{
if(f[u] != -1) //答案已经计算
{
return f[u];//返回计算过的答案
}
if(f == -1)
{
//各种玄学剪枝,此处省略20行
//应该计算了
for(/*一顿猛搜*/)
{
if(/*满足条件*/)
{
//改变条件
int k = dfs(u + 1);
f[u] = /*做一点处理*/;
//改变条件
}
}
return f[u];//结束
}
}
一般题目的板子不一定是这样,别照着抄,来几道题就明白了。
滑水雪
简称最大限度利用滑雪场并且让滑雪场亏本。
这道题暴力非常水,然后开开心心打完代码就$TLE$了。
暴力代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, a[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
int op = 1;
for(int i = 0; i < 4; i ++)
{
int px = x + dx[i], py = y + dy[i];
if(px <= 0 || px > n || py <= 0 || py > m) continue;
if(a[x][y] <= a[px][py]) continue;
op = max(op, dp(px, py) + 1);
}
return op;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1;j <= m; j ++)
cin >> a[i][j];
int res = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
res = max(res, dp(i, j));
cout << res;
}
全程乱搞,然后被整了。
于是我们加入f
数组,再看一下效果吧。
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, a[N][N], f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
int &op = f[x][y];
if(op != -1) return op;
op = 1;
for(int i = 0; i < 4; i ++)
{
int px = x + dx[i], py = y + dy[i];
if(px <= 0 || px > n || py <= 0 || py > m) continue;
if(a[x][y] <= a[px][py]) continue;
op = max(op, dp(px, py) + 1);
}
return op;
}
int main()
{
cin >> n >> m;
memset(f, -1, sizeof f);
for(int i = 1; i <= n; i ++)
for(int j = 1;j <= m; j ++)
cin >> a[i][j];
int res = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
res = max(res, dp(i, j));
cout << res;
}
一个小小的f
数组,就是$AC$的关键。
看来记忆化搜索的确能省去不少计算量,让时间变快。
but,这样会多用一部分空间。
这就是一个典型的例子:空间换时间。
很多算法也都是这么来的。
给个练习吧:天气预报
这个题大胆设就行了,代码复杂度稍微有点高,但不是很严重。
记忆化搜索是对dp的优化还是对dfs的优化啊佬
最后给的例题使我拍案叫绝
a 这
学到了学到了,我第一次看y总的视频就是滑雪,哈哈哈
qaq
嘿嘿
爆赞
感谢
写的很好
感谢
赞一个
谢谢