下面是一个朴素的棋盘上记忆化搜索代码(只是用来描述大致过程的,不是模板)
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;
}
这样改之后能不能通过减少函数的调用次数,减少栈内存的使用和卡常?如果可以,效果如何?