Rơi trứng siêu cấp trong C++

Cho K quả trứng, tòa nhà N tầng. Tìm số lần thả tối thiểu để xác định chính xác tầng F (trứng vỡ nếu thả từ tầng > F, không vỡ nếu ≤ F).

Ví dụ: K=2, N=6 → 3.

Giải thuật

1. DP với memoization: dp[K][N] = số lần thả tối thiểu.
2. Cơ sở: N ≤ 1 → N; K = 1 → N.
3. Chuyển trạng thái: thử thả tại tầng mid (tìm kiếm nhị phân trên mid):
   • left = 1 + solve(K-1, mid-1) (trứng vỡ).
   • right = 1 + solve(K, N-mid) (trứng không vỡ).
   • ret = min(ret, max(left, right)).
   • Điều chỉnh low/high dựa trên left vs right.
4. Trả về dp[K][N].

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> dp;
    int solve(int K, int N) {
        if (N <= 1) return N;
        if (K == 1) return N;
        if (dp[K][N] != -1) return dp[K][N];
        int ret = N, low = 0, high = N;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int left = 1 + solve(K - 1, mid - 1);
            int right = 1 + solve(K, N - mid);
            ret = min(ret, max(left, right));
            if (left == right) break;
            if (left < right) low = mid + 1;
            else high = mid - 1;
        }
        return dp[K][N] = ret;
    }
    int superEggDrop(int K, int N) {
        dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
        return solve(K, N);
    }
};
int main(){
    Solution ob;
    cout << (ob.superEggDrop(2,6));
}

Đầu vào

2, 6

Đầu ra

3