其實還是無法好好的解釋為什麼這樣可以 ！？
總之找了一個規律然後憑感覺寫？！XDDDDD
比較可能的解釋（？）
一樓的時候只需要丟一次
二樓的時候需要丟兩次
三樓的可能有(1+2)跟(2+1) 也就是拆成一樓跟二三樓；或是一二樓跟三樓
還是可以在兩次內找到。舉例來說：
從一樓丟: 破了-> 找到
沒破-> 從二樓丟，如果破了->答案是二樓；如果沒破，答案是三樓
四樓的時候，拆成二二或是一三；
二二的時候，從二樓丟或是從三樓丟是一樣的。
二丟 : 破了, 找到
沒破->只要再三樓再丟一次就可以找到, 拆成22的時候最少步數只要2.
來看拆成一三 :
從一丟：破了找到
沒破-> 二三四可以想成一個三樓再去拆，所以它最少要兩步
加上前面的從一樓丟，因此這時會變成三樓的最少丟數2次加上一次，去拆它變成兩半
五樓的時候拆成一四, 二三都還可以被前面cover, 所以一樣是3次
註: 拆成一四時，丟一樓破了就找到，沒破的話因為它還可以繼續用，就可以當成四樓的題目
又因為題目要找最少步數一定要找出答案，所以可以不用糾結拆成一四的時候步數其實比較多
六樓同理，到了七樓的時候，因為拆成3+4的時候需要多一個決定上半或下半的地方，因此要加一！（咦沒道理嗎XD）
換一種說法! 如果有n 樓，你取第k 樓丟第一發，
假使破了，剩下的就是從第一樓丟到第k-1 樓為worst case
假使沒破，那就是k+1樓到n樓為worst case
差不多就這樣啦(自暴自棄)
總之反推的話寫出來就降Orz
int twoEggDrop(int n){
int *dp=calloc(n+1,sizeof(int));
dp[1]=1;
if (n>1)
dp[2]=2;
int last=2;
for (int i=3;i<=n;i++)
{
if ((i - last) >= dp[i-1])
{
last=i;
dp[i]=dp[i-1]+1;
}
else
dp[i]=dp[i-1];
}
return dp[n];
}
#if 0
1: 1
2: 2
3:
4: 3 4-2=2
5:
6: 6-3=3
7: 4
8:
9:
10:
11: 5
16: 6
22: 7
29: 8
37: 9
46: 10
#endif
沒有留言:
張貼留言