About using a boolean array for memoization in a DP

Admin 1
Viewed 691

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/

memoization dynamic-programming algorithm
3 Answers

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.

user_140303530

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

user_9090950

In C# you can use nullable value types.

A nullable value type T? represents all values of its underlying value type T and an additional null value. For example, you can assign any of the following three values to a bool? variable: true, false, or null. An underlying value type T cannot be a nullable value type itself.

You can use null for indication of unvisited or unprocessed dp states.

you can simulate this in C++ by Initializing your dp memo to

vector<vector<bool*>> dp( m, vector<bool*>(n, nullptr) );

now you can use nullptr as an indicator for unprocessed dp states.

user_110621100
Related