Optimizing the Super Egg Drop Problem: A Dynamic Programming Approach

[algowhiz]

#include
#include
#include <limits.h>

using namespace std;

int superEggDrop(int k, int n) {
vector<vector> ans(k + 1, vector(n + 1, 0));

for (int i = 1; i <= k; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == 1) {
            ans[i][j] = j; 
        } else if (j == 1) {
            ans[i][j] = 1; 
        } else {
            int low = 1, high = j;
            while (low + 1 < high) {
                int mid = (low + high) / 2;

                int broken = ans[i - 1][mid - 1]; // Egg breaks
                int notBroken = ans[i][j - mid];   // Egg does not break

                if (broken > notBroken) {
                    high = mid;
                } else {
                    low = mid;
                }
            }

            // check both low and high
            ans[i][j] = 1 + min(max(ans[i - 1][low - 1], ans[i][j - low]),
                               max(ans[i - 1][high - 1], ans[i][j - high]));
        }
    }
}
return ans[k][n];

}