Dynamic Programming : Tabulation gives time out for some cases but memoization passes successfully.

[kapil2905]

Hi ppl :),

I was solving a DP problem and found that on submission, memoization technique passes the test where as tabulation fails.

The problem : given a set of +ve numbers S, and an integer N; find if there is a subset of the given set whose sum is equal to given integer N.

I understand that memoization calcualates only the required values whereas tabulation calculates entire table, hence tabulation can outperform memoization if the set S is small and integer N is large;
but I am looking
1) if there are any implementation issues or
2) any way to improve upon the tabulation version
3) Or this is the best tabulation possible in terms of run time complexity



Here is the code :

int memoizationUtil(long int N, long int m, std::vector<std::vector<int>>& dp, const std::vector<long int>& S)
{
    if (N < 0)    return 0;
    if (N == 0)   return 1;
    
    if (N > 0 && m <= 0)  return 0;
    
    if (dp.at(N-1).at(m-1) != -1) return dp.at(N-1).at(m-1);
    
    dp.at(N-1).at(m-1) = memoizationUtil(N-S.at(m-1), m-1, dp, S) ||
                           memoizationUtil(N, m-1, dp, S);
    
    return dp.at(N-1).at(m-1);
}

bool memoization(const std::vector<long int>& S, long int N)
{
    std::vector<std::vector<int>> dp(N);
    
    for (auto& it : dp)
    {
        it.assign(S.size(), -1);
    }
    
    return (bool)memoizationUtil(N, S.size(), dp, S);
}

bool tabulation(const std::vector<long int>& S, long int N)
{
    std::vector<std::vector<bool>> dp(N + 1);
    long int m = S.size();
    
    for (auto& it : dp)
    {
        it.assign(m + 1, false);
    }
    
    bool x{false}, y{false};
    
    for (register int i = 0; i <= N; ++i)
    {
        for (register int j = 0; j <= m; ++j)
        {
            if (i == 0) dp.at(i).at(j) = true;
            else if (j == 0) dp.at(i).at(j) = false;
            else
            {
            if (S.at(j-1) > i)  dp.at(i).at(j) = dp.at(i).at(j-1);
            if (S.at(j-1) <= i)   dp.at(i).at(j) = dp.at(i - S.at(j-1)).at(j-1)
                                                   || dp.at(i).at(j-1);
            }
        }
    }
    
    return dp.at(N).at(m);
}

bool Solve(const std::vector<long int>& S, long int N)
{
    if (N & 1)    return false;    //if N is odd, then no such subset is possible
    
    return memoization(S, N/2);  //works fine.
    //return tabulation(S, N/2);   //gives time out.
}

Thanks for any help :)