一、股票问题(*)
188.
买卖股票的最佳时机 IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i]
是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
labuladong算法秘籍中使用了【三个状态】（三维dp数组）
- 第几天
- 手中是否持有股票
- 最大交易限制（最大交易限制只在买入股票时减一）
状态转移方程
1
2
3
4
5
6
7
8
| dp[i][0][k] = Math.max(
dp[i-1][0][k],
dp[i-1][1][k]+prices[i-1]
);
dp[i][1][k] = Math.max(
dp[i-1][1][k],
dp[i-1][0][k-1]-prices[i-1]
);
|
base case
1
2
| dp[0][0][...] = 0; dp[0][1][...] = Integer.MIN_VALUE;
dp[...][0][0] = 0; dp[...][1][0] = Integer.MIN_VALUE;
|
二、打劫家舍问题
198.打劫家舍
213. 打家劫舍
II
337.
打家劫舍 III
1、打劫家舍
【状态】是 抢劫第i家时能获得的最大金额
1
2
|
dp[i] = Math.max(dp[i-2], dp[i-3]) + nums[i];
|
2、打劫家舍Ⅱ
特别之处在于 nums 换成了环形数组
应对策略也十分巧妙
\(f([x_{1}, x_{2}, ... , x_{n}]) = max(
f([x_{1}, x_{2}, ..., x_{n-1}]), f([x_{2}, ..., x_{n}]) )\)
既然首尾相连了，那么肯定最多只能抢劫一家，把另外一家除去，就把环形数组又变成了普通数组了。
3、打劫家舍Ⅲ
把家舍的形状变成了二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int rob(TreeNode root) {
int[] res = dp(root);
return Math.max(res[0], res[1]);
}
private int[] dp(TreeNode root){
if(root == null) return new int[]{0, 0};
int[] left = dp(root.left);
int[] right = dp(root.right);
int x = left[1] + right[1] + root.val;
int y = Math.max(left[1], left[0]) + Math.max(right[1], right[0]);
return new int[]{x, y};
}
}
|
三、博弈问题
486.
预测赢家
最核心最关键的还是在【找状态】，理解！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
dp[i][j][0] = Math.max(nums[i]+dp[i+1][j][1], nums[j]+dp[i][j-1][1]);
if 先手选择了i: dp[i][j][1] = dp[i+1][j][0];
if 先手选择了j: dp[i][j][1] = dp[i][j-1][0];
dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
|
四、扔鸡蛋（***）
887.鸡蛋掉落
这道题理解上难度很高...
这里讲一个逆向思维。
1
| dp[i][j] 表示有j个鸡蛋，可以操作i次，可以在最高dp[i][j]的建筑里保证找到f
|
比如dp[2][1]=2，表示有1个鸡蛋，可以操作2次，可以在最高2楼的建筑里保证找到f。意思就是如果楼>=3，就不能保证在1个鸡蛋2次操作的情况下找到f。这里的保证是指不管在什么情况下都可以成功找到f，而不是说有一定概率可以找到。很好理解，不管多高的楼层，即使给1个鸡蛋1次操作，也有一定概率可以找到f（第1层就碎了，所以f=0）
理解完状态之后，就需要找到状态转移方程。先给出来
1
| dp[i][j] = 1 + dp[i-1][j-1] + dp[i][j-1];
|
这里应该是这道题最难理解的地方。
五、自由之路
514.
自由之路
这道题一眼看去和普通的动态规划没什么区别，给定两个字符串，求某个最值。
但是这里的ring是环形的，而且可以顺时针/逆时针旋转，就导致每次的局部最优可能得不到全局最优，有点像回溯算法，需要走到更后面才能知道这一次的选择是否是更优的。
所以需要在每一步都要列出所有情况，在最后再选出最小的。
可以这么定义dp数组：
1
| dp[i][j] 表示 匹配key的第i个字符时 ring的第j个字符指向12:00 (当然了ring的第j个字符和key的第i个字符是相同的) 所需要的最小步数
|
状态转移方程
1
| dp[i][j] = Math.min( dp[i-1][k] + Math.min( Math.abs(j-k), n - Math.abs(j-k) ) ) k是ring中所有字符等于key[i-1]的下标集合
|
含义是：当用ring的第j个字符去匹配key的第i个字符时，所需要的最小步数应该这么求
列举出前一次匹配的所有情况\(dp[i-1][k], k
\in
[key的第i-1个字符在ring中的下标集合]\)，计算从每一次的情况走到当前情况需要的更小的步数（因为可以顺时针转也可以逆时针转），最后取这些情况的最小值。
完整代码如下：
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
| public int findRotateSteps(String ring, String key) {
int m = ring.length(); int n = key.length();
List<Integer>[] char2idx = new List[26];
for(int i = 0; i < 26; i++){
char2idx[i] = new ArrayList<>();
}
for(int i = 0; i < m; i++){
char2idx[ring.charAt(i) - 'a'].add(i);
}
int[][] dp = new int[n][m];
for(int i = 0; i < n; i ++) Arrays.fill(dp[i], 0x3f3f3f);
for(int i : char2idx[key.charAt(0) - 'a']){
dp[0][i] = Math.min( i, m-i ) + 1;
}
for(int i = 1; i < n; i++){
for(int j : char2idx[key.charAt(i) - 'a']){
for(int k : char2idx[key.charAt(i-1) - 'a']){
dp[i][j] = Math.min(
dp[i][j],
dp[i-1][k]
+ Math.min(
Math.abs(j-k),
m-Math.abs(j-k)
)
+ 1
);
}
}
}
return Arrays.stream(dp[n-1]).min().getAsInt();
}
|
六、K 站中转内最便宜的航班
787.K
站中转内最便宜的航班
image-20221112013403828
这道题既可以使用Dijkstra算法，也可以使用动态规划算法来解决。
这道题的起点和终点是确定的，在状态转移过程中选定一个不变，将另一个作为状态，然后另外一个状态就是中转站数k(或者使用边数来表示)
这里将src固定，将终点和中转站数作为状态，可以写出如下转移方程
\(price(k,dst) = min(price(k-1, v) +
val(v,dst))\)
v是距离dst还有一步的节点，\(val(v,dst)\)指边的价值
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
| List<int[]>[] graph;
int inf = 999999;
int src;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
this.src = src;
graph = new List[];
for(int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for(int[] flight : flights){
int from = flight[0];
int to = flight[1];
int price = flight[2];
graph[to].add(new int[]{from, price});
}
int[][] mem = new int[k+2][n];
for(int i = 0; i < k+2; i++) Arrays.fill(mem[i], inf);
int ans = dp(dst, k+1);
return ans == inf ? -1 : ans;
}
private int dp(int d, int k){
if(d == src) return 0;
if(k == 0) return inf;
if(mem[k][d] != inf){
return mem[k][d];
}
for(int[] prev : graph[d]){
int sub_ans = dp(prev[0], k-1);
mem[k][d] = Math.min(mem[k][d], sub_ans + prev[1]);
}
return mem[k][d];
}
|
还有一种更加简便的，去求所有从src开始走1步、2步、...、k+1步到达某节点的最小代价：使用dp[i][j]表示从src走i步到j节点所需要的最小代价。最后只要求\(min(dp[1][dst],
dp[2][dst],...,dp[k+1][dst])\)即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[][] dp = new int[k+2][n];
for(int i = 0; i <= k+1; i++) Arrays.fill(dp[i], 999999);
dp[0][src] = 0;
for(int i = 1; i <= k+1; i++){
for(int[] flight : flights){
int from = flight[0];
int to = flight[1];
int price = flight[2];
dp[i][to] = Math.min(dp[i][to], dp[i-1][from]+price);
}
}
int res = 999999;
for(int i = 1; i <= k+1; i++){
if(res > dp[i][dst]){
res = dp[i][dst];
}
}
return res == 999999 ? -1 : res;
}
|