動态規劃求解抛雞蛋問題(Google某年面試題)

摘要:假設現在某人手裡面有2個雞蛋,現在有一個200層的高樓,已知從某層樓和以上的樓層抛下雞蛋,就會使得雞蛋碎裂.求解用什麼樣的辦法可以使得抛雞蛋的次數最少.

(1)首先從程式設計的角度求解問題,這個問題是一個典型的動态規劃的問題.假設對于N層樓,手裡有2個雞蛋,所需要的最少的抛雞蛋次數是F(N)。那麼我們第一步一定是選擇某個樓層（第k層）抛一次雞蛋進行試探.F(N) = Min(F(N-k,2),k-1)+1(1=

(2)顯然如果直接根據遞歸的等式程式設計很簡單,但是會讓效率十分之低,因為這種方式相當于窮舉的思路.動态規劃之是以不同于窮舉,是因為它可以用很大的空間記錄已經求解的資料,是一種自底向上求解的過程.在這裡隻需要用一個數組作為輔助空間就可以大大減少計算.

#include "stdafx.h"
#define Number 200
#define Infinity 1000
int static F[Number] = {};
int max(int a,int b)
{
    return a>b?a:b;
}
void Find()
{
    int n,k,tmp;
    for (n = ;n<=Number-;n++)
    {
        F[n] = Infinity;
        for(k = ;k<=n;k++)
        {
            tmp = + max(k-,F[n-k]);
            F[n] = F[n] <tmp ?F[n]:tmp;
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    F[] = ;
    F[] = ;
    Find();
    return ;
}