CODEWITHSUNDEEP
c++algorithmdynamic-programmingmemoization
A. Sarid
A. Sarid

Reputation: 3996

Adding Memoization - Dynamic Programming

I am currently practicing some dynamic programming and I came across the Circus Tower problem.
I solved the problem with dynamic programming and implemented it using recursion. I've tested it with few inputs and it seems to work fine.

Now, I've been struggling few hours trying to figure out how to add memoization to my solution.

Questions

  1. How can I add a working memoization to my solution. Where is my mistake in this case?
  2. Is there any rule of thumb, or guidlines for how to add memoizations in general.

The Circus Tower Problem: A circus is designing a tower of people standing atop one another’s shoulders. Each person must be both shorter and lighter than the person below him. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

My Solution & Code
Dynamic Programming

OPT[N,P] = highest tower with N given persons and person P is at the top
----------------------------------------------------------
OPT[0,P]                                = 0
OPT[i,P] where person i can be above P  = max(OPT[i-1,i]+1,OPT[i-1,P])
OPT[i,P] else                           = OPT[i-1,P]

Code: 

struct Person{
    int ht;
    int wt;
};

// Without Memoization
int circusTower(int n, Person* top, std::vector<Person>& persons){
    if (n == 0)
        return 0;

    if (top == NULL || top->ht > persons[n - 1].ht && top->wt > persons[n - 1].wt)
        return max(circusTower(n - 1, &persons[n - 1], persons) + 1, circusTower(n - 1, top, persons));
    else
        return circusTower(n - 1, top, persons);
}

// With Memoization
int circusTower(int n, Person* top, std::vector<Person>& persons, std::vector<int>& memo){
    if (n == 0)
        return 0;

    int result;
    if (memo[n-1] == 0) {
        if (top == NULL || top->ht > persons[n - 1].ht && top->wt > persons[n - 1].wt)
            result = max(circusTower(n - 1, &persons[n - 1], persons, memo) + 1,
                         circusTower(n - 1, top, persons, memo));
        else
            result = circusTower(n - 1, top, persons, memo);

        memo[n - 1] = result;
        return result;
    } else {
        return memo[n-1];
    }
}

Main - test:

int main(){
    std::vector<Person> persons = { {65, 100},{100, 150},{56, 90}, {75, 190}, {60, 95},{68, 110} };
    std::stable_sort(persons.begin(), persons.end(), sortByWt);
    std::stable_sort(persons.begin(), persons.end(), sortByHt);

    std::vector<int> memo(6,0);

    //Without memoization
    cout << circusTower(6, NULL, persons) << endl;
    //With memoization
    cout << circusTower(6, NULL, persons, memo) << endl;
}

In the example inside the main above, the right result is 5. My regular solution (without memoization) prints 5, but with memoization it prints 6.

Upvotes: 1

Views: 716

Answers (1)

Jarod42
Jarod42

Reputation: 217275

Your method depend of 3 arguments but you memoize only from the first argument n

Indeed in your case, the third one (persons) is constant, but the second one (top) changes during the recursive call.

so due to your memoization, both the following return wrongly the same value:

  • circusTower(n - 1, &persons[n - 1], persons, memo)
  • circusTower(n - 1, top, persons, memo)

Upvotes: 2

Related Questions