VibhuSpeediest's blog

How to memoize a void function?
By VibhuSpeediest, history, 16 hours ago, In English

If I've written a function with a void return type and want to memoize it, how should I implement it?

void rec(int i, int flag, int sum, int& maxi, int n, vector<int>& arr, int count) {
        if (i == n) {
            if (count <= 4) {
                maxi = max(maxi, sum);
            }
            return;
        }
        if (flag) {
            rec(i + 1, 0, sum - arr[i], maxi, n, arr, count + 1);
            rec(i + 1, 1, sum, maxi, n, arr, count);
        } else {
            rec(i + 1, 1, sum + arr[i], maxi, n, arr, count + 1);
            rec(i + 1, 0, sum, maxi, n, arr, count);
        }
    }

How can I memoize this code?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 hours ago, # |
  Vote: I like it +12 Vote: I do not like it

Put this at the beginning of your function.

if (visited[i][flag][sum][count])
  return;
visited[i][flag][sum][count] = 1;
→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Won't it consume too much memory since a 4D array is being declared?

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If this is the case, you could treat the four variables together as an array and hash it, then define visited as an unordered_set.

      → Reply