有关记忆化搜索
  • 板块学术版
  • 楼主william_zy
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/4/3 17:10
  • 上次更新2023/10/28 04:44:10
查看原帖
有关记忆化搜索
201971
william_zy楼主2022/4/3 17:10

下面是一个朴素的棋盘上记忆化搜索代码(只是用来描述大致过程的,不是模板)

int dp[1010][1010];
const int dx[5]={0,1,0,-1,0};
const int dy[5]={0,0,1,0,-1};
int dfs(int x,int y){
  if(dp[x][y])return dp[x][y];
  if(...)return ...;
  int ans=0;
  ...
  int xx,yy;
  for(int i=1;i<=4;i++){
    xx=dx[i]+x;
    yy=dy[i]+y;
    if(...){
      ans+=dfs(xx,yy);
    }
  }
  return dp[x][y]=ans;
}

是不是可以把记忆化的部分改一个位置,

int dp[1010][1010];
const int dx[5]={0,1,0,-1,0};
const int dy[5]={0,0,1,0,-1};
int dfs(int x,int y){
//  if(dp[x][y])return dp[x][y];
  if(...)return ...;
  int ans=0;
  ...
  int xx,yy;
  for(int i=1;i<=4;i++){
    xx=dx[i]+x;
    yy=dy[i]+y;
    if(...){
      if(dp[xx][yy])
        ans+=dp[xx][yy];
      else
        ans+=(dp[xx][yy]=dfs(xx,yy));
    }
  }
  return /*dp[x][y]=*/ans;
}

这样改之后能不能通过减少函数的调用次数,减少栈内存的使用和卡常?如果可以,效果如何?

2022/4/3 17:10
加载中...