Skip to content

Memoization Search

Definition

Memoization search is a search implementation technique that avoids repeatedly traversing the same state by recording information about already visited states.

Because memoization search ensures each state is visited only once, it is also a common implementation method for dynamic programming.

Introduction

[NOIP2005] Herb Gathering

There are \(M\) different herbs in a cave. Picking each herb requires some time \(t_i\), and each herb has its own value \(v_i\). You are given a time period \(T\). Within this time, you can pick some herbs. Maximize the total value of the herbs collected.

\(1 \leq T \leq 10^3\), \(1 \leq t_i,v_i,M \leq 100\)

Naive DFS Approach

It is easy to implement a naive search approach: during the search, record three parameters—the current item to consider, the remaining time, and the accumulated value—then enumerate whether the current item is selected and transition to the corresponding state.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
int n, t;
int tcost[103], mget[103];
int ans = 0;

void dfs(int pos, int tleft, int tans) {
  if (tleft < 0) return;
  if (pos == n + 1) {
    ans = max(ans, tans);
    return;
  }
  dfs(pos + 1, tleft, tans);
  dfs(pos + 1, tleft - tcost[pos], tans + mget[pos]);
}

int main() {
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  dfs(1, t, 0);
  cout << ans << endl;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
tcost = [0] * 103
mget = [0] * 103
ans = 0


def dfs(pos, tleft, tans):
    global ans
    if tleft < 0:
        return
    if pos == n + 1:
        ans = max(ans, tans)
        return
    dfs(pos + 1, tleft, tans)
    dfs(pos + 1, tleft - tcost[pos], tans + mget[pos])


t, n = map(lambda x: int(x), input().split())
for i in range(1, n + 1):
    tcost[i], mget[i] = map(lambda x: int(x), input().split())
dfs(1, t, 0)
print(ans)

The time complexity of this approach is exponential, so it cannot pass this problem.

Optimization

Why is the above approach inefficient? Because the same state is visited multiple times.

If we store the information of a state after computing it, we can directly use the previously computed information when we need to access that state again, thus avoiding repeated calculations. This fully utilizes the characteristic of many problems in dynamic programming having a large number of overlapping subproblems, embodying the "memoization" idea of trading space for time.

Specifically for this problem, we add an array mem to the naive DFS to record the return value of each dfs(pos, tleft). Initially, set every value in mem to -1 (indicating not yet computed). Each time we need to access a state, if the corresponding value in mem is -1, we recursively compute that state. Otherwise, we directly use the value already stored in mem.

With this processing, we ensure each state is visited only once, so the time complexity of this algorithm is \(O(TM)\).

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, t;
int tcost[103], mget[103];
int mem[103][1003];

int dfs(int pos, int tleft) {
  if (mem[pos][tleft] != -1)
    return mem[pos][tleft];  // Already visited state, return the recorded value directly
  if (pos == n + 1) return mem[pos][tleft] = 0;
  int dfs1, dfs2 = -INF;
  dfs1 = dfs(pos + 1, tleft);
  if (tleft >= tcost[pos])
    dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];  // State transition
  return mem[pos][tleft] = max(dfs1, dfs2);  // Finally store the current state's value
}

int main() {
  memset(mem, -1, sizeof(mem));
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  cout << dfs(1, t) << endl;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
tcost = [0] * 103
mget = [0] * 103
mem = [[-1 for i in range(1003)] for j in range(103)]


def dfs(pos, tleft):
    if mem[pos][tleft] != -1:
        return mem[pos][tleft]
    if pos == n + 1:
        mem[pos][tleft] = 0
        return mem[pos][tleft]
    dfs1 = dfs2 = -INF
    dfs1 = dfs(pos + 1, tleft)
    if tleft >= tcost[pos]:
        dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos]
    mem[pos][tleft] = max(dfs1, dfs2)
    return mem[pos][tleft]


t, n = map(lambda x: int(x), input().split())
for i in range(1, n + 1):
    tcost[i], mget[i] = map(lambda x: int(x), input().split())
print(dfs(1, t))

Connection and Differences with Iterative DP

When solving dynamic programming problems, memoization search and iterative DP code are highly similar in form. This is because they use the same state representation and similar state transitions. Also because of this, generally the time complexities of the two implementations are the same.

Below is the iterative DP implementation code (for ease of comparison, rolling array optimization is not added). By comparison, you can find their formal similarity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int n, t, w[105], v[105], f[105][1005];

int main() {
  cin >> n >> t;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= t; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= w[i])
        f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);  // State transition equation
    }
  cout << f[n][t];
  return 0;
}

When solving dynamic programming problems, both memoization search and iterative DP ensure that each state is solved at most once. However, the way they achieve this differs slightly: iterative DP avoids repeated access by setting an explicit access order, while memoization search, although not explicitly specifying an access order, achieves the same goal by marking already visited states.

Compared to iterative DP, memoization search does not require an explicit access order, sometimes making it easier to implement than iterative DP, and it can handle boundary conditions more conveniently. This is a major advantage of memoization search. However, at the same time, memoization search is difficult to optimize with techniques like rolling arrays, and due to recursion, its runtime efficiency is lower than iterative DP. Therefore, the more suitable implementation method should be chosen based on the problem.

Method One

  1. Write down the DP state and equation for the problem.
  2. Write the dfs function based on them.
  3. Add the memoization array.

Example:

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

Convert to:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int dfs(int i) {
  if (mem[i] != -1) return mem[i];
  int ret = 1;
  for (int j = 1; j < i; j++)
    if (a[j] < a[i]) ret = max(ret, dfs(j) + 1);
  return mem[i] = ret;
}

int main() {
  memset(mem, -1, sizeof(mem));
  // Input part omitted
  int ret = 0;
  for (int j = 1; j <= n; j++) {
    ret = max(ret, dfs(j));
  }
  cout << ret << endl;
}

1
2
3
4
5
6
7
8
9
def dfs(i):
    if mem[i] != -1:
        return mem[i]
    ret = 1
    for j in range(1, i):
        if a[j] < a[i]:
            ret = max(ret, dfs(j) + 1)
    mem[i] = ret
    return mem[i]

Method Two

  1. Write a brute-force search program for the problem (preferably dfs).
  2. Modify this dfs into a "no external variables" dfs.
  3. Add the memoization array.

Example: The "Herb Gathering" example in this article.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用