- 业务限制模型特点：难以直观感受参数的范围。
- 从左到右，例如背包，参数就是weight
- 范围，范围就是L~R
- 样本对应，参数就是两样本各自的下标
象棋跳马问题
- 题目
- 棋盘从（0，0）到（9，10）的区域。马从（0，0）走k步落在（x，y）求有几种方法
- base case：区域限制，步数限制
- 接收信息：当前坐标 [i][j]，剩余步数 K
- 限制条件：马下一跳只能往八个点走
- 决策：八个点位依次调用
- 传递信息：[i][j]，K
- 优化记忆化搜索
- dp：i，j，rest（k）三个参数建造三维表
- base case：rest=0时，只有dp[0][x][y]=1
- 普遍位置依赖，每个点看下层的八个点位的way数累加和
- 代码
public static int waysdp(int a, int b, int s) {
int[][][] dp = new int[10][9][s + 1];
dp[a][b][0] = 1;
for (int step = 1; step <= s; step++) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 9; j++) {
dp[i][j][step] = getValue(dp, i - 2, j + 1, step - 1) + getValue(dp, i - 1, j + 2, step - 1)
+ getValue(dp, i + 1, j + 2, step - 1) + getValue(dp, i + 2, j + 1, step - 1)
+ getValue(dp, i + 2, j - 1, step - 1) + getValue(dp, i + 1, j - 2, step - 1)
+ getValue(dp, i - 1, j - 2, step - 1) + getValue(dp, i - 2, j - 1, step - 1);
}
}
}
return dp[0][0][s];
}
[[k步到达指定坐标]]
- 在M长的数组上移动，不能越界，K步后到达指定坐标
- 暴力递归思路：
- 传入信息（参数）：cur，aim，time。
- 决策：每个位置都往左右各调函数
- 限制：步数，左右边界
- base case：time=0时cur是不是aim，是则返回1，否则返回0
- 返回信息：走到aim的次数
-
暴力递归代码
```java
public static int ways1(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
return process1(start, K, aim, N);
}
// 机器人当前来到的位置是cur，
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
// 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
public static int process1(int cur, int rest, int aim, int N) {
if (rest == 0) { // 如果已经不需要走了，走完了！
return cur == aim ? 1 : 0;
}
// (cur, rest)
if (cur == 1) { // 1 -> 2
return process1(2, rest - 1, aim, N);
}
// (cur, rest)
if (cur == N) { // N-1 <- N
return process1(N - 1, rest - 1, aim, N);
}
// (cur, rest)
return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
}
```
- 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
- 记忆化搜索：缓存cur和time
-
public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
if (dp[cur][rest] != -1) {
return dp[cur][rest];
}
int ans = 0;
if (rest == 0) {
ans = cur == aim ? 1 : 0;
} else if (cur == 1) {
ans = process2(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process2(N - 1, rest - 1, aim, N, dp);
} else {
ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- dp，因为问题只和cur和time有关，所以time为x，cur为y建表
- 特殊位置x=0列，只有dp[0][aim]=1，其他为0 。
- 分析普遍位置依赖：dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
-
public static int ways3(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
dp[aim][0] = 1;
for (int rest = 1; rest <= K; rest++) {
dp[1][rest] = dp[2][rest - 1];
for (int cur = 2; cur < N; cur++) {
dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
}
dp[N][rest] = dp[N - 1][rest - 1];
}
return dp[start][K];
}
[[洗咖啡杯问题]]
- 题目
- N个人用arr[]台不同速度的咖啡机，洗杯子只有一台洗碗机需要时间a，杯子挥发需要时间b
- 给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间
给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡
只有一台洗咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
假设所有人拿到咖啡之后立刻喝干净，
返回从开始等到所有咖啡机变干净的最短时间
三个参数：int[] arr、int N，int a、int b
- 问题一、每个人最快喝完咖啡的时间
- 思路：时间为index咖啡机rest剩余工作时间+煮咖啡的时间cook=arr[index]。所以依据这个组合时间排序。
- 这组合时间的特点：rest部分会更改，cook不变。用定制比较器比较组合时间
- 流程：定制比较器，放小根堆里排序，每次弹出再放回
- 问题二、已经有出脏杯子的时间点了，怎么综合洗和挥发得到最佳时间
- 思路：洗time<挥发time时一定是综合两者能达到最佳时间
- 对每个杯子进行分析。
- 接收信息：index杯号，drink[index]接杯子可以洗的时间点，free洗碗机空闲的时间点，wash洗杯子的时间，air挥发杯子的时间，
- base case：index到末尾，retuen 0
- 决策：洗和挥发都调递归，index++，洗则推迟free
- 具体：p1洗：
- selfClean：当前杯子最迟结束的时间，max（drinks[index]，free）+wash
- restClean：当前杯子选择洗导致free时间推迟后，之后的杯子最迟结束的时间
- p1洗最迟结束（洗完的时间）=max（selfClean，restClean）
- p2不洗：
- selfClean=drinks[index]+wash
- restClean=index++，free没变
- 传出：min（p1，p2）
- 业务限制模型特点：难以直观感受参数的范围。
- 从左到右，例如背包，参数就是weight
- 范围，范围就是L~R
- 样本对应，参数就是两样本各自的下标
- dp：本题可变参数只有free，index。构建二维表（free，index）
- 问题：怎么确定maxFree？
- 答案：如果air
- 直接用drink[]中最大+wash（贪心）
- TODO 依赖没写
public static int bestTimeDp(int[] drinks, int wash, int air) {
int N = drinks.length;
int maxFree = 0;
for (int i = 0; i < drinks.length; i++) {
maxFree = Math.max(maxFree, drinks[i]) + wash;
}
int[][] dp = new int[N + 1][maxFree + 1];
for (int index = N - 1; index >= 0; index--) {
for (int free = 0; free <= maxFree; free++) {
int selfClean1 = Math.max(drinks[index], free) + wash;
if (selfClean1 > maxFree) {
break;
}
int restClean1 = dp[index + 1][selfClean1];
int p1 = Math.max(selfClean1, restClean1);
int selfClean2 = drinks[index] + air;
int restClean2 = dp[index + 1][free];
int p2 = Math.max(selfClean2, restClean2);
dp[index][free] = Math.min(p1, p2);
}
}
return dp[0][0];
}
- 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
[[51.N皇后问题]] #位运算
