I am solving a problem:

Given a list of integers nums, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative. For nums = [5, 1, 1, 5], output should be 10.

The dynamic programming logic that I have implemented is as below:

vector<pair<int,int>> dp;

int helper(vector<int>& nums, int i, bool include) {
    if(i>=nums.size()) return 0;
    pair<int,int> p=dp[i];
    if(p.first!=INT_MIN) return p.second;
    
    int maxval=0;
    if(include) maxval=nums[i] helper(nums,i 1,false);
    maxval=max(maxval,helper(nums,i 1,true));

    dp[i]=make_pair(include,maxval);
    return maxval;
}

int solve(vector<int>& nums) {
    dp.clear();
    dp.resize(nums.size(),make_pair(INT_MIN,INT_MIN));

    // For all -ve numbers in input, just return `0`, as required.
    int ans=max({helper(nums,0,true),helper(nums,0,false),0});

    //for(auto& p: dp) {
    //    cout<<p.first<<" "<<p.second<<"\n";
    //}

    return ans;
}

I get right answers when I don't do any memoization (so I think my recurrence relation is correct); but on memoizing it as above, I get wrong answers.

Logic that I am using for memoization: For the ith value, store a pair<int,int> in dp[i], where the first value of pair represents the boolean value include while the second value of pair represents the result maxvalue calculated for current value of i and include. Note that I use an int for a bool, since I need three values: true, false and "not yet calculated".

What am I missing in my memoization step? Any better way in which I could memoize it?

Thanks.

CodePudding user response：

int solve(const vector<int>& nums) {
    int N = nums.size();

    vector<int> dp(N, INT_MIN);
    function<int(int)> iter = [&](int i) {
        if(i>=N) { return 0; }
        if(dp[i] != INT_MIN) { return dp[i]; }
        return dp[i] = max(nums[i] iter(i 2), iter(i 1));
    };
    
    return iter(0);
}

CodePudding user response：

Don't overthink it. Memoizing a function f(P) { ... return Expr; } where P is a tuple of parameters is always the same. Add an outer (not local to the recursive function) map M from tuples P to return values. Then rewrite f as

f(P) {
  if M contains key P, return M[P];
  ...
  t = Expr;
  M[P] = t;
  return t;
}

It looks like in your function, nums never changes. So you can get away with omitting it from P. If the remaining parameters are an int and a bool, and the function returns int, then key tuples have type <int, bool>, and the map returns int. That is map<tuple<int, bool>, int>.

If the map key ends up being a natural number, and the possible range is small, then you can replace the memo map with an array initialized with some value that means "no value." Then the "contains key" test becomes a check whether M[P] is something different from "no value." In practical problems, this doesn't often happen.

I'll let you work out the rest, since it seems you're learning. A note is that in a proper implementation you wouldn't make the map a global variable. You'd wrap the recursive method in a class and make nums and the memo cache both fields so they don't need to be passed as parameters.