Skip to main content

Memoization / Top Down Approach

  1. dp function must be of backtracking(dfs) type and MUST have return type
  2. create recursive function with states -- returnType foo(STATES)
    • states only means variables that changes during recursion
  3. Write down the Recurrence Relation with base cases (TRANSITIONS)
  4. add a variable like ans = -1 for comparison purpose & then always UPDATE it likememo[row][bud] = ans;, So as to get the Most Optimized Solution
  5. the memo[][optmized value]
    • The column of the memo table MUST be the Optimization Value

✅ Parts of a Memoization Solution​

Gobal variables​

  1. input array/vector
  2. memo[][] or memo[] table to store already done dp(..) state values

parts of dp(...) function​

  1. Base case
  2. return value of the function dp(..) like
    • if (x == 0) return 0;

      it determines the dp(..) is returning a Count of steps or min/max` Amount

  3. declare ans variable
    • ans = -1e8
  4. use ans variable like for storing min(ans, ..) or max(ans, ..)
    • ans = min(ans, (dp(x-c) + 1) );
  5. for loop to traverse the given problem's array
    • for (auto c : coins) { ..
    • for (int k=1; k<v[row][0]; k++) { ..
  6. Update the memo[][] table with ans got after the for loop memo[..][..] = ans
  7. return ans

⭐ how to write recursive functions with return type​

memset()​

✅ use memset for single int values

int memo[MAX_gm][MAX_M]; // g < 20 and b <= 200

memset(memo, -1, sizeof memo); // TOP-DOWN: init memo

✅ assign()​

redeclaring the whole vector

// assign
memo.assign(MAX_gm, vector<int>(MAX_M, 0));

✅ fill()​

we must the ROW size

// fill
fill(memo.begin(), memo.end(), vector<int>(MAX_M, 1));

❌ clear() + resize()​

alwasy use v.assign() instead of this

// clear +  resize
memo.clear();
memo.resize(MAX_gm, vector<int>(MAX_M, -2));

⭐Ideal memoization DP Solution format​

int MAX_price = 210;
int MAX_gar = 30;
int MAX_K = 30;
int M, C;
vector<vector<int>> v(MAX_gar);
vector<vector<int>> memo(MAX_gar); // memo table

int dp(int row, int bud)    // only have STATES as parameters othe the DP function
{
    if (bud < 0)
        return -1e9;
    if (row == C)
        return M - bud; // bud is remaining budget
    if (memo[row][bud] != -1)
        return memo[row][bud];

    int ans = -1;

    for (int k = 1; k <= v.at(row).at(0); k++)
    {
        ans = max(ans, dp(row + 1, bud - v.at(row).at(k)));
    }

    memo[row][bud] = ans;   // update memo table [only after the for loop ends], so that all the values from EACH row has been taken

    return ans; // or 'return memo[row][bud]' BOTH are same right now we made ans the same as memo[row][bud]
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        fill(v.begin(), v.end(), vector<int>(MAX_K, -1));
        fill(memo.begin(), memo.end(), vector<int>(MAX_price, -1));
        cin >> M >> C;
        for (int row = 0; row < C; row++)
        {
            cin >> v.at(row).at(0);
            for (int i = 1; i <= v.at(row).at(0); i++)
            {
                cin >> v.at(row).at(i);
            }
        }

        int bud = M, row = 0;
        int ans = dp(row, bud);
        if (ans >= 0)
            cout << ans << endl;
        else
            cout << "no sol" << endl;
    }

    return 0;
}
/*
3

9 3
3 6 4 8
2 5 10
4 1 5 3 5

20 3
3 6 4 8
2 5 10
4 1 5 3 5

// no sol
// 19
 */

‼️💵 printing optimal choices in DP​

from CP book 4_i​

an example by CP_4_1
int MAX_price = 210;
int MAX_gar = 30;
int MAX_K = 30;
int M, C;
vector<vector<int>> v(MAX_gar);
vector<vector<int>> memo(MAX_gar); // table

int dp(int row, int bud)
{
    if (bud < 0)
        return -1e9;
    if (row == C)
        return M - bud; // bud is remaining budget
    if (memo[row][bud] != -1)
        return memo[row][bud];
    int ans = -1;
    for (int k = 1; k <= v.at(row).at(0); k++)
    {
        ans = max(ans, dp(row + 1, bud - v.at(row).at(k)));
    }
    memo[row][bud] = ans;
    return ans;
}

void print_dp(int row, int bud) // VOID function
{
    if ((row == C) || (bud < 0))
        return;                          // similar base cases
    for (int k = 1; k <= v[row][0]; ++k) // which model k is opt?
    {
        if (dp(row + 1, bud - v[row][k]) == memo[row][bud]) // using memo[][] created above in `dp()` function
        {
            cout << "- " << v[row][k] << " ";
            print_dp(row + 1, bud - v[row][k]); // recurse to this only
            break;
        }
    }
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        fill(v.begin(), v.end(), vector<int>(MAX_K, -1));
        fill(memo.begin(), memo.end(), vector<int>(MAX_price, -1));
        cin >> M >> C;
        for (int row = 0; row < C; row++)
        {
            cin >> v.at(row).at(0);
            for (int i = 1; i <= v.at(row).at(0); i++)
            {
                cin >> v.at(row).at(i);
            }
        }

        int bud = M, row = 0;
        int ans = dp(row, bud);
        if (ans >= 0)
            cout << ans << endl;
        else
            cout << "no sol" << endl;
        print_dp(row, bud);
    }

    return 0;
}
/*
3

9 3
3 6 4 8
2 5 10
4 1 5 3 5

20 3
3 6 4 8
2 5 10
4 1 5 3 5

// no sol
// - 6

// 19
// - 6 - 10 - 3 ✅
 */

Other Ways​

Problems of top-down approach:​

  • It occupies stack memory, which is limited
  • Stack memory is slow. One of the prime causes are, memory allocation is not performed at once but on demand
  • It occupies more memory as function information are stored too
  • To very few cases it's easy to think in tabular form
  • Tabular form by default uses memoization, thus code is much shorter