1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| struct Solution;
// @lc code=start
impl Solution {
/// ## 鸡蛋掉落
/// - 动态规划1(超时)
/// 1. 设 dp[i][j] 表示总共有i个鸡蛋, 总共j层楼时, 确定目标楼层f的最小操作次数;
/// 2. 如果最开始选择在x楼(1<=x<=j)扔1个鸡蛋, 此时会有两种情况：
/// a. 鸡蛋未破, 则目标楼层一定不在`[1,x)`中, 此时可继续用i个鸡蛋在`(x,n]`楼层中尝试.
/// 后续为确定目标楼层的最小操作次数为: dp[i][j-x]
/// b. 鸡蛋破裂, 则目标楼层一定不在`(x,j]`中, 此时可用剩下的i-1个鸡蛋在`[1,x)`楼层中继续尝试.
/// 后续为确定目标楼层的最小操作次数为: dp[i-1][x-1]
/// 综合以上情况, 如果扔1枚鸡蛋在x楼后, 为保证一定能确定目标楼层, 后续最小操作次数为:
/// max(dp[i][j-x], dp[i-1][x-1])
/// 那么, 依次从`[1,j]`中选择开始楼层x扔鸡蛋, 选择总操作数最小的即为dp[i][j]:
/// min(max(dp[i][j-x], dp[i-1][x-1]) + 1) ( 1 <= x <= j )
/// 3. 综上可得递推关系:
/// dp[i][j] = 1 + min(max(dp[i][j-k], dp[i-1][k-1])) ( 1 <= k <= j )
/// 4. 初始条件: 当只有1个鸡蛋时, 需要从低到高逐层进行尝试, 最坏情况需要到最高一层n才能确定,
/// 因此: dp[1][j] = j ( 1 <= j <= n )
/// 5. 目标值: dp[k][n]
pub fn super_egg_drop1(k: i32, n: i32) -> i32 {
let (k, n) = (k as usize, n as usize);
let mut dp = vec![vec![0; n as usize +1]; k as usize + 1];
// 初始条件
for j in 1..=n {
dp[1][j] = j;
}
for i in 2..=k {
for j in 2..=n {
dp[i][j] = 1 + (1..=j)
.map(|x|{
dp[i][j-x].max(dp[i-1][x-1])
})
.min()
.unwrap_or(1);
}
}
dp[k][n] as i32
}
/// ## 鸡蛋掉落
/// - 动态规划2
/// 1. 设 dp[i][j] 表示: 总共有i个鸡蛋, 扔鸡蛋j次, 最多可检测的楼层数;
/// 2. 扔1次鸡蛋后(不论扔在那个楼层), 有两种情况:
/// a. 鸡蛋未破, 剩余i个鸡蛋, 剩余操作次数j-1, 最多检测楼层数为: dp[i][j-1]
/// b. 鸡蛋破了, 剩余i-1个鸡蛋, 剩余操作次数j-1, 最多可检测楼层数为: dp[i-1][j-1]
/// 那么, 最多可检测楼层总数:
/// dp[i][j] = 1 + dp[i][j-1] + dp[i-1][j-1]
/// 3. 初始条件:
/// a. 鸡蛋个数i: 1 <= i <= k
/// a. 总操作次数j最多为楼层数: 1 <= j <= n;
/// b. 1个鸡蛋1次最多可检测楼层数为1: dp[1][1] = 1;
/// 4. 目标:
/// i, j 由小到大, 当: i == k && dp[i][j] >= n时, j的值
pub fn super_egg_drop(k: i32, n: i32) -> i32 {
let (k, n) = (k as usize, n as usize);
let mut dp = vec![vec![0; n + 1]; k + 1];
for i in 1..=k {
for j in 1..=n {
dp[i][j] = 1 + dp[i][j-1] + dp[i-1][j-1];
if i == k && dp[i][j] >= n {
return j as i32;
}
}
}
n as i32
}
}
// @lc code=end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::super_egg_drop(1, 2), 2);
assert_eq!(Solution::super_egg_drop(2, 6), 3);
assert_eq!(Solution::super_egg_drop(3, 14), 4);
assert_eq!(Solution::super_egg_drop1(1, 2), 2);
assert_eq!(Solution::super_egg_drop1(2, 6), 3);
assert_eq!(Solution::super_egg_drop1(3, 14), 4);
}
}
|