About using a boolean array for memoization in a DP

Question

I have a working recursive solution to a DP problem. I wish to memoize it.

Currently it depends on two states: the index i and a boolean variable true or false.

Could someone please point out how I could memoize it? Specifically, how I could initialize the memoization table (dp)?

I am confused because if I initialize the second state with false, I wouldn't be able to differentiate between the false that is due to initialization, versus the one where it is actually the value of the state.

Could someone please provide some advise?

Thanks.

To clarify further: This is how I declare the dp table right now:

vector<vector < bool > > dp;

How do I initialize the inner vector<bool>? I don't think I can set it to either true or false since I wouldn't be able to distinguish later if that is the value generated while executing (solving the problem) or the initialization value.

Edit: Adding the code:

class Solution {
public:
    unordered_map<int, int> m1, m2;
    vector<int> n1, n2;
    vector<vector<int>> v;
    
    int helper(int i, bool parsingNums1) {
        if((parsingNums1 && i>=n1.size()) || (!parsingNums1 && i>=n2.size())) return v[i][parsingNums1]=0;
        if(v[i][parsingNums1]!=-1) return v[i][parsingNums1];
        
        int ans=0;
        
        if(parsingNums1) {
            //we are traversing path 1
            //see if we can switch to path 2
            if(m2.find(n1[i])!=m2.end())
                ans=n1[i] + helper(m2[n1[i]]+1, false);
            ans=max(ans, n1[i] + helper(i+1, true));
        }

        if(!parsingNums1) {
            //we are traversing path 2
            //see if we can switch to path 1
            if(m1.find(n2[i])!=m1.end())
                ans=n2[i] + helper(m1[n2[i]]+1, true);
            ans=max(ans, n2[i] + helper(i+1, false));
        }

        return v[i][parsingNums1]=ans;
    }
    
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        for(int i=0; i<nums1.size(); i++)
            m1[nums1[i]]=i;
        for(int i=0; i<nums2.size(); i++)
            m2[nums2[i]]=i;
        n1=nums1;
        n2=nums2;
        v.resize((nums1.size()>nums2.size()?nums1.size()+1:nums2.size()+1), vector<int>(2,-1));
        
        return max(helper(0, true), helper(0, false))%(int)(1e9+7);
    }
};

I am solving this LeetCode question: https://leetcode.com/problems/get-the-maximum-score/

Answer 1

There are 2 easy methods for handling this.

1. Declare another vector<vector < bool > > is_stored which is initialised as 0 and when dp[i][j] is calculated, mark is_stored[i][j] as 1. So when you are checking wether the particular state is being memorized, you can look into the is_stored.

2. Use vector< vector < int > > instead of vector< vector < bool > > and initialise -1 to every state to mark as not memorised.

Answer 2

Another way to store values is using Map<String, Boolean> map = new HashMap<String, Boolean>(); // just a java version

then you can create key by appending i & j and store respective boolean value to that key. for example

String key = i + ',' + j;

// To validate if we calculated data before

if(map.containsKeys(key)) return map.get(key);

// To store/memoize values
boolean result = someDPmethod(); map.put(key, result);