Doubt in Memoization

[utkarsh1729]

I was solving the Little Elephant and T-Shirts problem (TSHIRTS Problem - CodeChef). With the help of the editorial I wrote the following code. But I have some doubts regarding it.

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define mod 1000000007

bool table[105][15];
ll dp[1030][105];

ll solve(int mask, int id, int n)
{
    if(mask == ((1<<n)-1))
        return dp[mask][id] = 1;
    if(id == 101)
        return 0;
    if(dp[mask][id] != -1)
        return dp[mask][id];

    ll ways = 0;
    ways += solve(mask,id+1,n);

    rep(p,1,n+1)
    {
        if(mask&(1<<(p-1)))
            continue;
        if(table[id][p])
        {
            ways += solve(mask|(1<<(p-1)),id+1,n);
            if(ways >= mod) ways -= mod;
        }
    }
    return dp[mask][id] = ways;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(table,false,sizeof(table));
        memset(dp,-1,sizeof(dp));
        int n;
        cin >> n;
        string s;
        stringstream ss;
        int x;
        cin.ignore();
        rep(i,1,n+1)
        {
            getline(cin,s);
            ss << s;
            while(ss >> x)
                table[x][i] = true;
            ss.clear();
        }
//        rep(i,0,10)
//        {
//            rep(j,0,10)
//                cout << table[i][j] << " ";
//            cout << "\n";
//        }
        cout << solve(0,1,n) << "\n";
    }
    return 0;
}

In the above code, there are two base cases which I am unable to understand. Not the base cases themselves but the way they are handled. In the first case when mask is equal to (1<<n)-1 we set dp[mask][id] as 1 and return it, why can’t we simply return 1 as dp[mask][id] = ways ultimately. Alright, then in the second case, when id is equal to 101 instead of setting dp[mask][id] as something we simply return 0. So do we do this just because we have to return something when we run out of T-shirts or is it important to return 0 only.
I think I still don’t understand memoization completely and how it actually works. Please help.

[ashu12_chi]

I have not solved the problem, but answering you in general, id = 101 is out of range case so you can not get any answer if id reaches this value, in the program you have declared dp table large in size enough to save this in your dp array but in general it is useless. Similarly, mask = (1<<n)-1 is base condition on which you are getting answer to be honest since you are checking dp[mask][id] != -1 after it, it is also useless to save in your case.

[utkarsh1729]

@ashu12_chi Thanks for your response. But this is how the editorial describes the solution. The code provided there uses the same cases (rather I have used them from there only). It would be great if you could explain how one should approach DP the memoization way.

[ashu12_chi]

When you are using memoization approach in dp, what you are actually doing is calling a recursive function to solve your problem (also known as top down approach). I will try to explain in few points:

1. First you should understand that dp is an approach to optimise this recursive function by saving previously called recursive calls.
2. Even if you don’t use memoization, only calling recursive function will solve your problem and give you correct answer. (Verify this by running following program on sample input of problem)

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define mod 1000000007

bool table[105][15];
//ll dp[1030][105];

ll solve(int mask, int id, int n)
{
    if(mask == ((1<<n)-1))
        return 1;
    if(id == 101)
        return 0;

    ll ways = 0;
    ways += solve(mask,id+1,n);

    rep(p,1,n+1)
    {
        if(mask&(1<<(p-1)))
            continue;
        if(table[id][p])
        {
            ways += solve(mask|(1<<(p-1)),id+1,n);
            if(ways >= mod) ways -= mod;
        }
    }
    return ways;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(table,false,sizeof(table));
        //memset(dp,-1,sizeof(dp));
        int n;
        cin >> n;
        string s;
        stringstream ss;
        int x;
        cin.ignore();
        rep(i,1,n+1)
        {
            getline(cin,s);
            ss << s;
            while(ss >> x)
                table[x][i] = true;
            ss.clear();
        }
//        rep(i,0,10)
//        {
//            rep(j,0,10)
//                cout << table[i][j] << " ";
//            cout << "\n";
//        }
        cout << solve(0,1,n) << "\n";
    }
    return 0;
}

3. Then question is why dp or memoization. Actually when you will submit it or run on large test cases it will take much time and give you TLE.
4. Question is why? Because you are calculating same function again and again in recursive calls. So, instead of calling same function again and again it is better to save it’s result first time you calculate it and from next time just use the saved result.
5. For better understanding take example of Fibonacci series when you want to calcualate Fib(5) you will be needed Fib(4) and Fib(3) and for Fib(4), you will use Fib(3) and Fib(2). Just see here you need Fib(3) twice. See this image:
   
   
6. Finally, how to approach a problem using dp + memoization just try to figure out the recursive function and then save recursive calls in dp table.
7. Final suggestion for better understanding about which recursive function will be actually requiring memoization you should try to read more about overlapping sub problems. e.g. Fibonacci series.

[utkarsh1729]

Thanks a lot @ashu12_chi Thanks for your efforts.