扔鸡蛋(Egg dropping)

1. /// # Egg Dropping Puzzle

3. /// `egg_drop(eggs, floors)` returns the least number of egg droppings
4. ///     required to determine the highest floor from which an egg will not
5. ///     break upon dropping
6. ///
7. /// Assumptions: n > 0
8. pub fn egg_drop(eggs: u32, floors: u32) -> u32 {
9. assert!(eggs > 0);

11. // Explicity handle edge cases (optional)
12. if eggs == 1 || floors == 0 || floors == 1 {
13. return floors;
14. }

16. let eggs_index = eggs as usize;
17. let floors_index = floors as usize;

19. // Store solutions to subproblems in 2D Vec,
20. // where egg_drops[i][j] represents the solution to the egg dropping
21. // problem with i eggs and j floors
22. let mut egg_drops: Vec<Vec<u32>> = vec![vec![0; floors_index + 1]; eggs_index + 1];

24. // Assign solutions for egg_drop(n, 0) = 0, egg_drop(n, 1) = 1
25. for egg_drop in egg_drops.iter_mut().skip(1) {
26. egg_drop[0] = 0;
27. egg_drop[1] = 1;
28. }

30. // Assign solutions to egg_drop(1, k) = k
31. for j in 1..=floors_index {
32. egg_drops[1][j] = j as u32;
33. }

35. // Complete solutions vector using optimal substructure property
36. for i in 2..=eggs_index {
37. for j in 2..=floors_index {
38. egg_drops[i][j] = std::u32::MAX;

40. for k in 1..=j {
41. let res = 1 + std::cmp::max(egg_drops[i - 1][k - 1], egg_drops[i][j - k]);

43. if res < egg_drops[i][j] {
44. egg_drops[i][j] = res;
45. }
46. }
47. }
48. }

50. egg_drops[eggs_index][floors_index]
51. }

53. #[cfg(test)]
54. mod tests {
55. use super::egg_drop;

57. #[test]
58. fn zero_floors() {
59. assert_eq!(egg_drop(5, 0), 0);
60. }

62. #[test]
63. fn one_egg() {
64. assert_eq!(egg_drop(1, 8), 8);
65. }

67. #[test]
68. fn eggs2_floors2() {
69. assert_eq!(egg_drop(2, 2), 2);
70. }

72. #[test]
73. fn eggs3_floors5() {
74. assert_eq!(egg_drop(3, 5), 3);
75. }

77. #[test]
78. fn eggs2_floors10() {
79. assert_eq!(egg_drop(2, 10), 4);
80. }

82. #[test]
83. fn eggs2_floors36() {
84. assert_eq!(egg_drop(2, 36), 8);
85. }

87. #[test]
88. fn large_floors() {
89. assert_eq!(egg_drop(2, 100), 14);
90. }
91. }