-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDp887.java
More file actions
154 lines (138 loc) · 5.5 KB
/
Dp887.java
File metadata and controls
154 lines (138 loc) · 5.5 KB
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package dynamicprogramming;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* @ProjectName: leetcode
* @Package: dynamicprogramming
* @ClassName: Dp887
* @Author: markey
* @Description:887. 鸡蛋掉落
* 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
*
* 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
*
* 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
*
* 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
*
* 你的目标是确切地知道 F 的值是多少。
*
* 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
*
*
*
* 示例 1：
*
* 输入：K = 1, N = 2
* 输出：2
* 解释：
* 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
* 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
* 如果它没碎，那么我们肯定知道 F = 2 。
* 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
* 示例 2：
*
* 输入：K = 2, N = 6
* 输出：3
* 示例 3：
*
* 输入：K = 3, N = 14
* 输出：4
*
*
* 提示：
*
* 1 <= K <= 100
* 1 <= N <= 10000
* 通过次数17,253提交次数64,795
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/super-egg-drop
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* @Date: 2020/4/11 22:18
* @Version: 1.0
*/
public class Dp887 {
public static void main(String[] args) {
System.out.println(superEggDrop(2, 6));
System.out.println(superEggDrop1(2, 6));
}
public static int superEggDrop(int K, int N) {
// dp[i][j]：一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少实验的次数
// 注意：
// 1、i 表示的是楼层的大小，不是第几层的意思，例如楼层区间 [8, 9, 10] 的大小为 3，这一点是在状态转移的过程中调整的定义
// 2、j 表示可以使用的鸡蛋的个数，它是约束条件，我个人习惯放在后面的维度，表示消除后效性的意思
// 0 个楼层和 0 个鸡蛋的情况都需要算上去，虽然没有实际的意义，但是作为递推的起点，被其它状态值所参考
int[][] dp = new int[N + 1][K + 1];
// 由于求的是最小值，因此初始化的时候赋值为一个较大的数，9999 或者 i 都可以
for (int i = 0; i <= N; i++) {
Arrays.fill(dp[i], i);
}
// 初始化：填写下标为 0、1 的行和下标为 0、1 的列
// 第 0 行：楼层为 0 的时候，不管鸡蛋个数多少，都测试不出鸡蛋的 F 值，故全为 0
for (int j = 0; j <= K; j++) {
dp[0][j] = 0;
}
// 第 1 行：楼层为 1 的时候，0 个鸡蛋的时候，扔 0 次，1 个以及 1 个鸡蛋以上只需要扔 1 次
dp[1][0] = 0;
for (int j = 1; j <= K; j++) {
dp[1][j] = 1;
}
// 第 0 列：鸡蛋个数为 0 的时候，不管楼层为多少，也测试不出鸡蛋的 F 值，故全为 0
// 第 1 列：鸡蛋个数为 1 的时候，这是一种极端情况，要试出 F 值，最少次数就等于楼层高度（想想复杂度的定义）
for (int i = 0; i <= N; i++) {
dp[i][0] = 0;
dp[i][1] = i;
}
for (int i = 0; i <= N; i++) {
System.out.println(Arrays.toString(dp[i]));
}
System.out.println();
// 从第 2 行，第 2 列开始填表
for (int i = 2; i <= N; i++) {
for (int j = 2; j <= K; j++) {
for (int k = 1; k <= i; k++) {
// 碎了，就需要往低层继续扔：层数少 1 ，鸡蛋也少 1
// 不碎，就需要往高层继续扔：层数是当前层到最高层的距离差，鸡蛋数量不少
// 两种情况都做了一次尝试，所以加 1
dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
}
}
}
for (int i = 0; i <= N; i++) {
System.out.println(Arrays.toString(dp[i]));
}
return dp[N][K];
}
public static int superEggDrop1(int K, int N) {
// 表示有K个鸡蛋和N层时的最优解
int[][] dp = new int[K+1][N+1];
// 只有一个鸡蛋时，只能线性遍历；
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K ; j++) {
dp[j][i] = i;
}
}
// 只有1层楼时，不管有多少个鸡蛋只需要扔一次
for (int i = 1; i <= K; i++) {
dp[i][1] = 1;
}
for (int i = 0; i <= K; i++) {
System.out.println(Arrays.toString(dp[i]));
}
System.out.println();
// 状态转移时，
for (int i = 2; i <= K; i++) {
for (int j = 2; j <= N; j++) {
for (int k = 1; k <= j; k++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][j - k], dp[i-1][k-1]) + 1);
}
}
}
for (int i = 0; i <= K; i++) {
System.out.println(Arrays.toString(dp[i]));
}
return dp[K][N];
}
}