主页双贴危
您学过记忆化吗？这个记忆化不是非常直接。。。
by jingkongwanglimiaoa @ 2021-09-29 22:54:34
记忆化是记忆化了，但是过不过就不一定了
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,p,q;
long long sum;
int h[25][25]; //记忆化数组
int zu(int x,int y){
if(h[x][y]!=0){
return h[x][y];
}
if(x==n&&y==m){
sum++;
return h[x][y]=1;
}
if(x==p-1&&y==q-2){
return h[x][y]=1;
}
if(x==p-2&&y==q-1){
return h[x][y]=1;
}
if(x==p+1&&y==q-2){
return h[x][y]=1;
}
if(x==p+2&&y==q-1){
return h[x][y]=1;
}
if(x==p-2&&y==q+1){
return h[x][y]=1;
}
if(x==p-1&&y==q+2){
return h[x][y]=1;
}
if(x==p+1&&y==q+2){
return h[x][y]=1;
}
if(x==p+2&&y==q+1){
return h[x][y]=1;
}
if(x==p&&y==q){
return h[x][y]=1;
}
if(x==n){
return h[x][y]=zu(x,y+1);
}
if(y==m){
return h[x][y]=zu(x+1,y);
}
return h[x][y]=zu(x+1,y)+zu(x,y+1);
}
int main(){
cin>>n>>m>>p>>q;
zu(0,0);
cout<<sum;
return 0;
}
```
爆零，给我整蒙了，我是不是写个假的记忆化？
by songxiao @ 2021-09-29 22:57:13
@[jingkongwanglimiaoa](/user/222578) @[SpadeA261](/user/124218)
求大佬帮我看一下
by songxiao @ 2021-09-29 22:58:57
@[Gorilla](/user/307912) 你等等 我给你改改
但是你没发现你的sum还是只会++而根本没有用到记忆化数组吗
by jingkongwanglimiaoa @ 2021-09-29 23:40:11
记忆化一个是避免重复运算的操作
对于这道题，这个“重复运算操作”就在于sum++，也就是说，记忆化数组h[x][y] 要当第二次（或更多次）搜索到x,y时，直接返回你sum需要加多少
那么看回你的暴力代码，发现你只有在第一个条件判断 sum++了，于是只有在第一个函数要返回1（并存储到记忆化数组里），后面一堆返回1的应该是返回0
那么回到h[x][y]的定义为遍历到x,y时它后面答案要+多少，初始进入dfs(0,0)
那么输出的答案可以看作为h[0][0]
~~您的代码过于丑陋 实在懒得改~~
by jingkongwanglimiaoa @ 2021-09-29 23:47:20
```cpp
#include <bits/stdc++.h>
#define maxn 105
using namespace std;
bool vis[maxn][maxn];
long long int target[maxn][maxn];//记录是否踩过
long long x, y, ans = 0;
long long dfs(long long X, long long Y)
{ //x,y坐标
if (vis[X][Y] || X > x || Y > y)
return 0;
// cout << X << " " << Y << "x,y\n";
if(target[X][Y]){
ans+=target[X][Y];
return target[X][Y];
}
// target[X][Y] = true;
if(X==x && Y == y){
target[X][Y]++;
ans++;
return 1;
}
// vis[X][Y] = true;
long long int first = dfs(X + 1, Y), second = dfs(X, Y + 1);
if (first || second){
target[X][Y]+=first+second;
return first+second;
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int hx, hy;
cin >> x >> y >> hx >> hy;
vis[hx][hy]=true;
vis[hx - 1][hy + 2] = vis[hx + 1][hy + 2] = vis[hx - 2][hy + 1] = vis[hx + 2][hy + 1] = vis[hx + 2][hy - 1] = vis[hx - 2][hy - 1] = vis[hx - 1][hy - 2] = vis[hx + 1][hy - 2] = true;
dfs(0, 0);
cout << ans;
return 0;
}
```
用记忆化写的target记录的是这个到终点的数
by liuyushen @ 2021-10-06 08:16:42