动态规划-常见做法：记忆化搜索

时间：2024-02-01 21:23:57

记忆化搜索

引入

记忆化搜索，是最容易写,也是效率较高的一种做法。
虽然本质上是DFS这种搜索的思路，但其对搜索过的状态进行记录，从而完成对未知状态的推导，实际上也是一种DP的思想。

例题-滑雪

洛谷P1434 [SHOI2002]滑雪（传送门）

题目描述
Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可行的滑坡为24－17－16－1（从24开始，在1结束）。当然25－24－23－...－3－2－1更长。事实上，这是最长的一条。

输入输出格式
输入格式：
输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。
输出格式：
输出区域中最长滑坡的长度。

输入输出样例
输入样例#1：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例#1：
25

思路

暴搜挂着机

乍一看，这不是一道水题吗？
~~问：兔*除了水博客，他还会干什么？
答：唱、跳、搞事情。~~

该题让我们找一条最长的路
其实我们枚举出发点，从出发点向四周扩展即可解题
于是蒟蒻的兔子花了5分钟，打出了代码

#include <bits/stdc++.h>
using namespace std;
int read(){//快读，不用管它，了解详见(https://blog.csdn.net/P2718756941/article/details/95048385)
    int x=0,f=1;
    char ch=getchar();//getchar()读入单个字符（包括空格 ，换行符）
    while(ch<'0'||ch>'9'){//非数字（字符）
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);//原二进制数向左平移x位，右边原位置以0补齐(位运算）
        ch=getchar();
    }
    return x*f;
}//PQH式专属快读
int n,m;
int a[1010][1010];
int ans,ans2;//全图最长，枚举一点 
void CIN(){//输入
    n=read();//快读输入
    m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
        } 
    }
    return;
}
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//行走方向
bool in(int x,int y){//检查是否在图中
    if(x>0&&y>0&&x<=n&&y<=m)return 1;
    return 0;
}
int DFS(int x,int y){//DFS日常
    int mx=0;
    for(int i=0;i<4;i++){//四个方向
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(in(xx,yy)&&a[x][y]>a[xx][yy]){
            mx=max(mx,DFS(xx,yy));//比较择最长
        }
    }
    ans2=mx+1;
    return ans2;
}
int main(){
    CIN();
    for(int i=1;i<=n;i++){//枚举
        for(int j=1;j<=n;j++){
            ans=max(ans,DFS(i,j));
        }
    }
    cout<<ans;
    return 0;
}

但是，你会发现一个神奇的事情
您TME了：）

只得了90分，挺满意的
兔子才没有这么蒟蒻

搜索正解

刚刚的暴搜确实很暴力，但好在还是过了9组测试数据
仔细思考（足足花了兔子三秒钟呢 ），于是决定写动归。
无脑推一波动态转移方程，什么，没有？？
状态并不是固定的，于是，我们需要用到记忆化搜索。
记忆化搜索，其实就是用搜索的方式，替换了动归只会按照循环遍历而对状态转移方位不确定的图无法完成的缺点(好像这句话不通，不要在意这些细节 ）
记忆化搜索，结合动归记录之前状态的优点。
记忆化搜索可以排除一些无效状态，但动归总要遍历所有的状态。
记忆化搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上比动态规划要低很多。
所以，记忆化搜索才是王道。
在这里插入图片描述
上图是搜索思路，于是我们可以得到以下记忆化搜索

int a[1010][1010];
int dp[1010][1010];
int DFS(int x,int y){
    if(dp[x][y]>1)return dp[x][y];
    for(int i=0;i<4;i++){
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(in(xx,yy)&&a[x][y]>a[xx][yy]){
            dp[x][y]=max(dp[x][y],DFS(xx,yy)+1);
        }
    }
    return dp[x][y];
}

按这个思路打一遍，于是就AC了
在这里插入图片描述

AC代码

#include <bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();//getchar()读入单个字符（包括空格 ，换行符）
    while(ch<'0'||ch>'9'){//非数字（字符）
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);//原二进制数向左平移x位，右边原位置以0补齐(位运算）
        ch=getchar();
    }
    return x*f;
}//PQH式专属快读
 
 
int n,m;
int a[1010][1010];
int dp[1010][1010];
int ans;
 
void CIN(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            dp[i][j]=1;
        } 
    }
    return;
}
 
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
 
bool in(int x,int y){
    if(x>0&&y>0&&x<=n&&y<=m)return 1;
    return 0;
}
 
int DFS(int x,int y){
    if(dp[x][y]>1)return dp[x][y];
    for(int i=0;i<4;i++){
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(in(xx,yy)&&a[x][y]>a[xx][yy]){
            dp[x][y]=max(dp[x][y],DFS(xx,yy)+1);
        }
    }
 
     
    return dp[x][y];
}
 
int main(){
    CIN();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max(ans,DFS(i,j));
        }
    }
     
    cout<<ans<<endl;
     
     
    return 0;
}

推荐刷题

洛谷P1464 Function（传送门）

相关文章