记忆化搜索

ryf_loser · 2022-12-10 21:09:42 · 题解

此题建议评绿。

此题正解记忆化搜索或者动态规划。

如果此题爆搜，仅仅拿到一半的分数。

动态规划思路在此题解中并不讲述。

记忆化搜索是对某一种重复出现情况进行记录。

此题我们要明确递归参数是什么，通过探究我们可以得知： x,y 表示所在位置，maxx 表示手里有的物品的最大值，step 表示共取了多少个物品。

则递归就是 dfs(x,y,maxx,step)。

对于记忆化数组，也是记录 s[x][y][maxx][step] 的值，因为记忆化搜索原理，记录与此节点相似节点的值，然后直接返回即可。

根据记忆化搜索易得程序。

AC CODE

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,k,a[60][60],s[60][60][15][15];
int dfs(int x,int y,int maxx,int step){
    if (x==n+1||y==m+1)return 0;//边界条件。
    if (s[x][y][maxx+1][step]!=-1)return s[x][y][maxx+1][step];//记忆化搜索。
    long long cnt=0;
    if (x==n&&y==m){
        if (step==k||(step==k-1&&a[x][y]>maxx))
            cnt++;
    }
    else {
        cnt+=dfs(x,y+1,maxx,step);
        if (a[x][y]>maxx)cnt+=dfs(x,y+1,a[x][y],step+1);
        cnt+=dfs(x+1,y,maxx,step);
        if (a[x][y]>maxx)cnt+=dfs(x+1,y,a[x][y],step+1);//怎样搜索。
    }
    s[x][y][maxx+1][step]=cnt%1000000007;
    return s[x][y][maxx+1][step];
}
int main(){
    scanf ("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf ("%d",&a[i][j]);//读入
    memset(s,-1,sizeof(s));//赋值为 -1。
    printf ("%d",dfs(1,1,-1,0));
    return 0;
}