Rompecabezas de los huevos | conjunto 2

Dados N huevos y K pisos, la tarea es encontrar el número mínimo de intentos necesarios, en el peor de los casos, para encontrar el piso debajo del cual todos los pisos son seguros. Un piso es seguro si dejar caer un huevo no lo rompe. Consulte n huevos y k pisos para obtener más información.

Ejemplos: 

Entrada: N = 2, K = 10 
Salida: 4 
Explicación: 
La primera prueba fue en el cuarto ^piso . Dos casos surgen después de esto:

1. Si el huevo se rompe, nos queda un huevo, por lo que necesitamos tres intentos más.
2. Si el huevo no se rompe, el siguiente intento es desde el 7º piso. De nuevo surgen dos casos.

Entrada: N = 2, K = 100 
Salida: 14

Prerrequisitos: Rompecabezas de caída de huevos
Enfoque: Considere este problema de una manera diferente: 
Sea dp[x][n] el número máximo de pisos que se pueden controlar con n huevos y x movimientos dados.
Entonces la ecuación es: 

1. Si el huevo se rompe, podemos verificar dp[x – 1][n – 1] pisos.
2. Si el huevo no se rompe, podemos verificar dp[x – 1][n] + 1 pisos.

Como necesitamos cubrir k pisos, dp[x][n] >= k.
dp[x][n] es similar al número de combinaciones y aumenta exponencialmente a k
A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number
// of trials needed in the worst case
// with n eggs and k floors
int eggDrop(int n, int k)
{
    vector<vector<int> > dp(k + 1, vector<int>(n + 1, 0));
 
    int x = 0;
 
    // Fill all the entries in table using
    // optimal substructure property
    while (dp[x][n] < k) {
 
        x++;
        for (int i = 1; i <= n; i++)
            dp[x][i] = dp[x - 1][i - 1] + dp[x - 1][i] + 1;
    }
 
    // Return the minimum number of moves
    return x;
}
 
// Driver code
int main()
{
    int n = 2, k = 36;
 
    cout << eggDrop(n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the minimum number
// of trials needed in the worst case
// with n eggs and k floors
static int eggDrop(int n, int k)
{
    int dp[][] = new int [k + 1][n + 1];
 
    int x = 0;
 
    // Fill all the entries in table using
    // optimal substructure property
    while (dp[x][n] < k)
    {
 
        x++;
        for (int i = 1; i <= n; i++)
            dp[x][i] = dp[x - 1][i - 1] +
                       dp[x - 1][i] + 1;
    }
 
    // Return the minimum number of moves
    return x;
}
 
// Driver code
public static void main(String args[])
{
    int n = 2, k = 36;
 
    System.out.println( eggDrop(n, k));
}
}
 
// This code is contributed by Arnab Kundu

# Python implementation of the approach
 
# Function to return the minimum number
# of trials needed in the worst case
# with n eggs and k floors
def eggDrop(n, k):
    dp = [[0 for i in range(n + 1)] for
           j in range(k + 1)]
 
    x = 0;
 
    # Fill all the entries in table using
    # optimal substructure property
    while (dp[x][n] < k):
 
        x += 1;
        for i in range(1, n + 1):
            dp[x][i] = dp[x - 1][i - 1] + \
                        dp[x - 1][i] + 1;
     
    # Return the minimum number of moves
    return x;
 
# Driver code
if __name__ == '__main__':
    n = 2; k = 36;
 
    print(eggDrop(n, k));
 
# This code is contributed by PrinciRaj1992

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the minimum number
// of trials needed in the worst case
// with n eggs and k floors
static int eggDrop(int n, int k)
{
    int [,]dp = new int [k + 1, n + 1];
 
    int x = 0;
 
    // Fill all the entries in table using
    // optimal substructure property
    while (dp[x, n] < k)
    {
 
        x++;
        for (int i = 1; i <= n; i++)
            dp[x, i] = dp[x - 1, i - 1] +
                    dp[x - 1, i] + 1;
    }
 
    // Return the minimum number of moves
    return x;
}
 
// Driver code
public static void Main(String []args)
{
    int n = 2, k = 36;
 
    Console.WriteLine(eggDrop(n, k));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript implementation of the approach
 
// Function to return the minimum number
// of trials needed in the worst case
// with n eggs and k floors
function eggDrop(n, k)
{
    let dp = new Array();
 
    for(let i = 0; i < k + 1; i++){
        dp.push(new Array(n + 1).fill(0))
    }
 
    let x = 0;
 
    // Fill all the entries in table using
    // optimal substructure property
    while (dp[x][n] < k) {
 
        x++;
        for (let i = 1; i <= n; i++)
            dp[x][i] = dp[x - 1][i - 1] + dp[x - 1][i] + 1;
    }
 
    // Return the minimum number of moves
    return x;
}
 
// Driver code
let n = 2, k = 36;
document.write(eggDrop(n, k));
</script>

8

Complejidad de tiempo: O(NlogK) 
Complejidad de espacio: O(N * K)