VibhuSpeediest's blog

How to memoize a void function?
By VibhuSpeediest, history, 14 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
  • -2
  • Vote: I do not like it

»
9 hours ago, # |
  Vote: I like it +10 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
  • »
    »
    6 minutes 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