算法总结——记忆化搜索（进阶）

· · 算法·理论

记忆化搜索是搜索的一个优化，可以避免多次求同一个子问题的答案。今天我们用它来求解一些更复杂的问题。

例题1：P1164 小A点菜

这题是01背包求方案数的模板题，我们按照记忆化搜索三步法开始实现：

  1. 搜索状态：dfs(x,y)返回前x个物品装入一个容量为y的背包的合法方案数
  2. 状态转移：
    • 装得下(w_i\le y)：dfs(x-1,y)+dfs(x-1,y-w_i)
    • 装不下(w_i > y)：dfs(x-1,y)
  3. 初始状态：
    • #### 代码: ```cpp #include <bits/stdc++.h> using namespace std;

long long n,m,a[105],ans[105][10005],vis[105][10005];

long long dfs(int x,int y) { if(x < 0 || y < 0) return 0; if(vis[x][y] == 1) return ans[x][y]; if(x == 0 && y == 0) return 1; vis[x][y] = 1; if(y >= a[x]) return ans[x][y] = dfs(x-1,y-a[x])+dfs(x-1,y); return ans[x][y] = dfs(x-1,y); }

int main(void) { cin >> n >> m; for(int i = 1;i <= n;i++) cin >> a[i]; cout << dfs(n,m); return 0; }

### 例题2：[P1002 [NOIP2002 普及组] 过河卒](https://www.luogu.com.cn/problem/P1002)
#### 这题也是求方案数，我们还是按照记忆化搜索三步法开始实现：
1. 搜索状态：$dfs(x,y)$返回前从点$(0,0)$到点$(x,y)$合法方案数
2. 状态转移：
- 此处不是马的控制点：$dfs(x-1,y)+dfs(x,y-1)$因为按照题面，上一步只可能是点$(x-1,y)$或是点$(x,y-1)$。
- 此处是马的控制点：$0$因为卒一到这里就被马吃了，不能躲避，所以合法方案数为$0$
- 此处是第$1$行：$dfs(x-1,y)$因为$y$不能为负数
- 此处是第$1$列：$dfs(x-1,y)$因为$x$不能为负数
3. 初始状态：
- $1$   $(x=0,y=0)$ 从点$(0,0)$到点$(0,0)$有一种方案
- $0$   $(所有非法状态)$ 表示非法状态都没有合法答案
### 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;

long long n,m,house_x,house_y,ans[25][25];
bool vis[25][25];
const long long dx[8] = {1,1,-1,-1,2,-2,2,-2};
const long long dy[8] = {2,-2,2,-2,1,1,-1,-1};

long long dfs(long long x,long long y)
{
    if(vis[x][y] == 1) return ans[x][y];
    if(x == 0 && y == 0) return ans[x][y] = 1;
    if(x == 0) return ans[x][y] = dfs(x,y-1);
    if(y == 0) return ans[x][y] = dfs(x-1,y);
    vis[x][y] = 1;
    return ans[x][y] = dfs(x-1,y) + dfs(x,y-1);
}

int main(void)
{
    cin >> n >> m >> house_x >> house_y;
    vis[house_x][house_y] = 1;
    for(long long i = 0;i < 8;i++)
    {
        long long nx = house_x+dx[i],ny = house_y+dy[i];
        if(nx < 0 || ny < 0) continue;
        vis[nx][ny] = 1;
        ans[nx][ny] = 0;
    }
    cout << dfs(n,m);
    return 0;
}