定义

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。

引入

题目描述

山洞里有 M 株不同的草药，采每一株都需要一些时间 t_i，每一株也有它自身的价值 v_i。给你一段时间 T，在这段时间里，你可以采到一些草药。让采到的草药的总价值最大。

暴力DFS做法

很容易实现这样一个朴素的搜索做法：在搜索时记录下当前准备选第几个物品、剩余的时间是多少、已经获得的价值是多少这三个参数，然后枚举当前物品是否被选，转移到相应的状态。

struct node {
    int time;
    int value;
    node() = default;
    node(int time, int value) : time(time), value(value) {}
};

node arr[105];

int T, M;
int ans = 0;
void dfs(int index, int sumTime, int sumValue) {
    if (sumTime > T) return;
    if (index == M) {
        ans = max(ans, sumValue);
        return;
    }
    dfs(index + 1, sumTime + arr[index].time, sumValue + arr[index].value);
    dfs(index + 1, sumTime, sumValue);
}

int main() {
    cin >> T >> M;
    for (int i = 0; i < M; i++) {
        cin >> arr[i].time;
        cin >> arr[i].value;
    }
    dfs(0, 0, 0);
    cout << ans << endl;
}

这种做法的时间复杂度是指数级别的，并不能通过本题。

优化

上面的做法为什么效率低下呢？因为同一个状态会被访问多次。

如果我们每查询完一个状态后将该状态的信息存储下来，再次需要访问这个状态就可以直接使用之前计算得到的信息，从而避免重复计算。这充分利用了动态规划中很多问题具有大量重叠子问题的特点，属于用空间换时间的「记忆化」思想。

具体到本题上，我们在朴素的 DFS 的基础上，增加一个数组 mem 来记录每个 dfs(pos,tleft) 的返回值。刚开始把 mem 中每个值都设成 -1（代表没求解过）。每次需要访问一个状态时，如果相应状态的值在 mem 中为 -1，则递归访问该状态。否则我们直接使用 mem 中已经存储过的值即可。

通过这样的处理，我们确保了每个状态只会被访问一次，因此该算法的的时间复杂度为 O™。

struct node {
    int time;
    int val;
    node() = default;
};

node arr[105];
int memo[105][1005];

int T, M;
int dfs(int index, int sumTime) {
    if (memo[index][sumTime] != -1) return memo[index][sumTime];
    if (index == M) return memo[index][sumTime] = 0;
    int dfs1;
    int dfs2 = INT_MIN;
    dfs1 = dfs(index + 1, sumTime);
    if (sumTime + arr[index].time <= T)
        dfs2 = dfs(index + 1, sumTime + arr[index].time) + arr[index].val;
    return memo[index][sumTime] = max(dfs1, dfs2);
}

int main() {
    cin >> T >> M;
    memset(memo, -1, sizeof(memo));
    for (int i = 0; i < M; i++) {
        cin >> arr[i].time;
        cin >> arr[i].val;
    }
    cout << dfs(0, 0) << endl;
}

与递推的联系与区别

在求解动态规划的问题时，记忆化搜索与递推的代码，在形式上是高度类似的。这是由于它们使用了相同的状态表示方式和类似的状态转移。也正因为如此，一般来说两种实现的时间复杂度是一样的。

下面给出的是递推实现的代码（为了方便对比，没有添加滚动数组优化），通过对比可以发现二者在形式上的类似性。

struct node {
    int time;
    int val;
    node() = default;
};

node arr[105];
int dp[105][1005];

int T, M;

int main() {
    cin >> T >> M;
    for (int i = 0; i <= T; i++) dp[0][i] = 0;
    for (int i = 1; i <= M; i++) {
        cin >> arr[i].time;
        cin >> arr[i].val;
    }
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j <= T; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= arr[i].time)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i].time] + arr[i].val);
        }
    }
    cout << dp[M][T];
}

在求解动态规划的问题时，记忆化搜索和递推，都确保了同一状态至多只被求解一次。而它们实现这一点的方式则略有不同：递推通过设置明确的访问顺序来避免重复访问，记忆化搜索虽然没有明确规定访问顺序，但通过给已经访问过的状态打标记的方式，也达到了同样的目的。

与递推相比，记忆化搜索因为不用明确规定访问顺序，在实现难度上有时低于递推，且能比较方便地处理边界情况，这是记忆化搜索的一大优势。但与此同时，记忆化搜索难以使用滚动数组等优化，且由于存在递归，运行效率会低于递推。因此应该视题目选择更适合的实现方式。

如何写记忆化搜索

方法一

把这道题的 dp 状态和方程写出来
根据它们写出 dfs 函数
添加记忆化数组

举例：

最长上升子序列

$dp_{i} = \max\{dp_{j}+1\}\quad (1 \leq j < i \land a_{j}<a_{i})$

class Solution {
    vector<int> memo;
    int dfs(vector<int>& nums, int i) {
        if (memo[i] != -1) return memo[i];
        int ret = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) ret = max(ret, dfs(nums, j) + 1);
        }
        return memo[i] = ret;
    }
public:
    int lengthOfLIS(vector<int>& nums) {
        memo = vector<int>(nums.size() - 1, -1);
        int ret = 1;
        for (int i = 1; i < nums.size(); i++) {
            ret = max(ret, dfs(nums, i));
        }
        return ret;
    }
};