Memoized Search

Definition

Memoized search is a search implementation that records information about states already visited, thereby avoiding visiting the same state repeatedly.

Because memoized search ensures that each state is visited only once, it is also a common way to implement dynamic programming.

Introduction

Naive DFS approach

It is easy to implement a naive search: during the search, record the three parameters—the index of the item currently being considered, the remaining time, and the value obtained so far—then enumerate whether the current item is selected and transition to the corresponding states.

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;
}

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 approach above inefficient? Because the same state is visited multiple times.

If we store the information of a state after querying it, then when that state needs to be visited again, we can directly use the previously computed result and avoid recomputation. This makes full use of the fact that many dynamic-programming problems have a large number of overlapping subproblems, and is the space-for-time idea of “memoization”.

For this problem, on top of the naive DFS, add an array mem to record the return value of every dfs(pos,tleft). Initially, set every value in mem to -1 (meaning that it has not been solved). Whenever a state is visited, if its corresponding value in mem is -1, recursively visit that state. Otherwise, directly use the value already stored in mem.

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

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];  // The state has been visited; return its 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 value of the current state
}

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;
}

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))

Relation to and difference from bottom-up recurrence

When solving a dynamic-programming problem, the code for memoized search and the code for a bottom-up recurrence are highly similar in form. This is because they use the same state representation and similar state transitions. For this reason, the time complexities of the two implementations are generally the same.

Here is a bottom-up recurrence implementation (without rolling-array optimization, for ease of comparison). Comparing them shows the similarity in form:

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 a dynamic-programming problem, both memoized search and a bottom-up recurrence ensure that each state is solved at most once. Their ways of achieving this differ slightly: the recurrence avoids repeated visits by specifying an explicit access order, while memoized search has no explicitly prescribed order but achieves the same goal by marking states that have already been visited.

Compared with a recurrence, memoized search sometimes has lower implementation difficulty because it does not require an explicit access order, and it can handle boundary cases relatively conveniently. This is a major advantage of memoized search. At the same time, memoized search is difficult to optimize with rolling arrays and runs less efficiently because of recursion. Therefore, choose the more suitable implementation according to the problem.

How to write memoized search

Method 1

1. Write the dp states and recurrence for the problem.
2. Write the dfs function based on them.
3. Add a memoization array.

Example:

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

Convert it to:

C++

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));
  // Omitted: input
  int ret = 0;
  for (int j = 1; j <= n; j++) {
    ret = max(ret, dfs(j));
  }
  cout << ret << endl;
}

Python

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 2

1. Write the brute-force program for the problem (preferably dfs).
2. Change this dfs into a dfs that does not use external variables.
3. Add a memoization array.

Example: the “Collecting Herbs” example in this article