跟蹤表中刪除

Question

兩個蛋的問題：

您將得到2個雞蛋。
您可以使用100層高的建築物。
雞蛋可能非常硬或非常脆弱，意味着如果從一樓掉下來，雞蛋可能會破損，或者如果從100層跌落，雞蛋可能不會破損。兩個雞蛋都是相同的。
你需要弄清100層建築物的最高樓層，雞蛋可以放下而不會斷裂。
現在的問題是你需要做多少滴。你可以在這個過程中打破2個雞蛋。

我知道動態規劃這個問題的解決方案。我想跟蹤解決方案以及最少的嘗試次數。即我必須嘗試獲得最少的嘗試次數。

# include <stdio.h> 
# include <limits.h> 


// A utility function to get maximum of two integers 
int max(int a, int b) { return (a > b)? a: b; } 


/* Function to get minimum number of trails needed in worst 
    case with n eggs and k floors */ 
int eggDrop(int n, int k) 
{ 
    /* A 2D table where entery eggFloor[i][j] will represent minimum 
     number of trials needed for i eggs and j floors. */ 
    int eggFloor[n+1][k+1]; 
    int res; 
    int i, j, x; 

    // We need one trial for one floor and0 trials for 0 floors 
    for (i = 1; i <= n; i++) 
    { 
     eggFloor[i][1] = 1; 
     eggFloor[i][0] = 0; 
    } 

    // We always need j trials for one egg and j floors. 
    for (j = 1; j <= k; j++) 
     eggFloor[1][j] = j; 

    // Fill rest of the entries in table using optimal substructure 
    // property 
    for (i = 2; i <= n; i++) 
    { 
     for (j = 2; j <= k; j++) 
     { 
      eggFloor[i][j] = INT_MAX; 
      for (x = 1; x <= j; x++) 
      { 
       res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]); 
       if (res < eggFloor[i][j]) 
        eggFloor[i][j] = res; 
      } 
     } 
    } 

    // eggFloor[n][k] holds the result 
    return eggFloor[n][k]; 
} 

/* Driver program to test to pront printDups*/ 
int main() 
{ 
    int n = 2, k = 36; 
    printf ("\nMinimum number of trials in worst case with %d eggs and " 
      "%d floors is %d \n", n, k, eggDrop(n, k)); 
    return 0; 
} 

Answer 1

你只需要存儲x的，讓你的最佳解決方案的價值：

int eggDrop(int n, int k) 
{ 
    /* A 2D table where entery eggFloor[i][j] will represent minimum 
     number of trials needed for i eggs and j floors. */ 
    int eggFloor[n+1][k+1]; 
    int floor[n+1][k+1]; 
    int res; 
    int i, j, x; 

    // We need one trial for one floor and0 trials for 0 floors 
    for (i = 1; i <= n; i++) 
    { 
     eggFloor[i][1] = 1; 
     eggFloor[i][0] = 0; 
    } 

    // We always need j trials for one egg and j floors. 
    for (j = 1; j <= k; j++) 
     eggFloor[1][j] = j; 

    // Fill rest of the entries in table using optimal substructure 
    // property 
    for (i = 2; i <= n; i++) 
    { 
     for (j = 2; j <= k; j++) 
     { 
      eggFloor[i][j] = INT_MAX; 
      for (x = 1; x <= j; x++) 
      { 
       res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]); 
       if (res < eggFloor[i][j]) { 
        eggFloor[i][j] = res; 
        floor[i][j] = x; 
       }       
      } 
     } 
    } 

    // eggFloor[n][k] holds the result 
    return eggFloor[n][k]; 
} 

最後，樓[i] [j]包含你需要嘗試你的時候地板我有雞蛋和j層。