Egg Drop Problem

#include<algorithm>
#include<iostream>
#include<climits>
#include<map>

using namespace std;

int EggDrops (int eggs, int floors) {

    int cache[eggs+1][floors+1];

    // If there are no floors (i.e 0 floors) we would have zero attempts.
    // If there is only 1 floor, there would only be 1 attempt.
    for (int e=0; e<=eggs; e++) {
        cache[e][0] = 0;
        cache[e][1] = 1;
    }

    // If there is only 1 egg then we could need attempts 
    // same as the number of floors in worst case.
    // If there are 0 eggs, there would be 0 attempts.
    for (int f=0; f<=floors; f++) {
        cache[1][f] = f;
        cache[0][f] = 0;
    }

    /*
    floors  k   | 
            .   |
            .   |
            f   | <- If an egg breaks at floor f, then we would need to check the floors below 'f'
           f-1  |    to find the bottom-most floor from which an egg if dropped would break.
            .   |    i.e (f-1) floors with one less egg from available eggs.
            2   |    If the egg doesn't break, then we would need to check the floors above f
            1   |    i.e from floor f + 1 till n i.e (k-f) floors with the same number of eggs. 

        Note : If an egg breaks or it doesn't break, every drop is considered an attempt.
    */

    for (int e=2; e<=eggs; e++) {
        for (int f=2; f<=floors; f++) {
            cache[e][f] = INT_MAX;
            for (int current_floor = 2; current_floor <= f; current_floor++) {
                // On the current floor there are two possible scenarios (Egg breaks, Egg doesn't break).
                int attempts = 1 + max(cache[e-1][current_floor-1], cache[e][f-current_floor]);
                cache[e][f] = min(cache[e][f], attempts);
            }
        }
    }

    return cache[eggs][floors];
}

map<pair<int, int>, int> cache_map;
int EggDropsRec (int eggs, int floors) {

    if (eggs == 1)
        return floors;

    if (floors == 0 || floors == 1)
        return floors;

    if (cache_map.find(make_pair(eggs, floors)) != cache_map.end()) {
        return cache_map.find(make_pair(eggs, floors))->second;
    }

    int attempt = INT_MAX;
    for (int current_floor=1; current_floor<=floors; current_floor++) {
        // Two possibilities 
        // 1.Egg breaks 
        // 2.Egg doesn't break
        attempt = min(attempt, 1 + max(EggDropsRec(eggs-1, current_floor-1), EggDropsRec(eggs, floors-current_floor)));
    }
    cache_map.insert(make_pair(make_pair(eggs, floors), attempt));
    return attempt;
}

int main() {

    int eggs = 2, floors = 300;
    cout << "Dynamic Programming" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDrops(eggs, floors) << endl;
    cout << "Recursion" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDropsRec(eggs, floors) << endl;

    eggs = 5, floors = 100;
    cout << "\nDynamic Programming" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDrops(eggs, floors) << endl;
    cout << "Recursion" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDropsRec(eggs, floors) << endl;

    return 0;
}

Dynamic Programming
Eggs : 2 Floors : 300 Attempts required : 24
Recursion
Eggs : 2 Floors : 300 Attempts required : 24

Dynamic Programming
Eggs : 5 Floors : 100 Attempts required : 7
Recursion
Eggs : 5 Floors : 100 Attempts required : 7