https://wenku.baidu.com/view/7c9de809581b6bd97f19ea72.html
鷹蛋問(wèn)題
兩顆蛋:考慮sqrt(n)的方式逐個(gè)扔蛋
M顆蛋,N層樓:
(1)動(dòng)態(tài)規(guī)劃,O(MNN)=O(N3)
f(i,j) = min{max(f(i-1, w-1), f(i, j-w))|1<=w<=j} + 1
(2)優(yōu)化,當(dāng)M>log2(N),使用二分法最壞情況下的最小次數(shù)必然是log2(N+1);故只需考慮M<=log2(N)的情況,復(fù)雜度降低為O(N2logN)