双蛋问题 (The Two Egg Problem) || 鹰蛋问题
问题问题
100层楼,底层扔鸡蛋不会碎，高层扔鸡蛋会碎，有M个蛋，最少扔多少次可以找到临界层？
最坏情况下
- 1.一个鸡蛋的时候 从 1楼开始扔，最坏情况 100 次
- 2.无数个鸡蛋时，二分法，50 25 12 6 3 2 1，最坏情况 7 次
- 3.两个鸡蛋时，10 20 30 40 50 60 70 80 90 100 最坏情况 10 + 9 次
- 4.两个鸡蛋时，k k-1,k-2,k-3—-1, (k + 1) * k / 2>=100,k = 14,
14 27 39 50 60 69 77 84 90 95 99 100 最坏情况 14 次 - 5.f(i,j) i 代表鸡蛋个数,j代表楼层
f(i,j)=min(max(f(i,f-1) + 1,f(i-1,j-f)+1)) i<=f<=j
根据函数使k,n规划可计算出结果 k—-
| i\j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 |
| 3 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
| 4 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
| 5 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
| 9 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
fMedian 的计算二分查找
- 1.T1 = dp[i - 1][f - 1] 是单调递增函数
- 2.T2 = dp[i][j - f] 是单调递减函数
- 3.max(dp[i - 1][f - 1],dp[i][j - f]),就是两个函数的交点
- 4.交点可能是浮点数，如果是整数，fmin=fmax=fmedian 如果是浮点数，离散化，求出交点位置的左右点
特征
线段截断，将问题分成两段的子问题，递归解决
0/1背包问题，n个物品的问题通过n-1个物品的问题叠加求解
如何通过问题寻找子问题，怎么定位子问题
f(n,m) 与 f(n-k1,m) f(n,m-k2)之间的函数关系