forked from dairongpeng/algorithm-note
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path12.md
More file actions
1172 lines (939 loc) · 38.9 KB
/
12.md
File metadata and controls
1172 lines (939 loc) · 38.9 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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
- [1 暴力递归到动态规划](#1)
* [1.1 例一 : 机器人运动问题(2018阿里面试题目)](#11)
* [1.2 例二：背包问题改动态规划](#12)
* [1.3 动态规划解题思路](#13)
+ [1.3.1 凑货币问题（重要）](#131)
+ [1.3.2 贴纸问题](#132)
* [1.4 什么暴力递归可以继续优化？](#14)
* [1.5 暴力地柜和动态规划的关系](#15)
* [1.6 面试题中和动态规划的关系](#16)
* [1.7 如何找到某个问题的动态规划方式？](#17)
* [1.8 面试中设计暴力递归过程的原则](#18)
* [1.9 笔试面试过程中怎么设计暴力递归？](#19)
* [1.10 常见的4种尝试模型](#110)
+ [1.10.1 从左往右的尝试模型](#1101)
+ [1.10.2 范围上的尝试模型](#1102)
+ [1.10.3 多样本位置全对应的尝试模型](#1103)
- [1.10.3.1 两个字符串的最长公共子序列问题](#11031)
+ [1.10.4 寻找业务限制的尝试模型](#1104)
* [1.11 如何分析有没有重复解](#111)
* [1.12 暴力递归到动态规划的套路](#112)
* [1.13 动态规划的进一步优化](#113)
<h1 id='1'>1 暴力递归到动态规划</h1>
==动态规划最核心的是暴力递归的尝试过程，一旦通过尝试写出来暴力递归的解法，那么动态规划在此基础上就很好改了==
> 1、暴力递归之所以暴力，是因为存在大量的重复计算。加入我们定义我们的缓存结构，用来查该状态有没有计算过，那么会加速我们的递归
> 2、在我们加入缓存结构之后，消除了大量的重复计算，缓存表就是我们的dp表。那么这种去除重复计算的递归，就是最粗糙的动态规划，也叫记忆化搜索
> 3、如果我们把我们的dp表，从简单到复杂列出来，那么就是经典的动态规划。我们无需考虑转移方程怎么写，而是根据我们的递归来推导。看下面例子：
<h2 id='11'>1.1 例一 : 机器人运动问题(2018阿里面试题目)</h2>
> 认识暴力递归改动态规划的过程
假设有排成一行的N个位置，记为1~N,N一定大于等于2。开始时机器人在其中的M位置上（M一定是1~N中的一个）。
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N-1的位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走K步，最终能来到P位置（P也是1~N中的一个）的方法有多少种？
给定四个参数N,M,K,P。返回方法数
> 暴力递归ways1调用的walk函数，就是暴力递归过程，存在重复计算。waysCache方法对应的walkCache就是在纯暴力递归的基础上加了缓存
==假设我们的参数N=7，M=2,K=5,P=3。我们根据我们的递归加缓存的过程来填我们的dp表：==
1、int[][] dp = new int[N+1][K+1];是我们的DP表的范围
2、当rest==0的时候，dp[cur][rest] = cur == P ? 1 : 0; 我们只有cur==P的时候为1,其他位置都为0。
3、当cur==1的时候，dp[cur][rest] = walkCache(N, 2, rest - 1, P, dp); 我们的dp当前的值，依赖于cur的下一个位置，rest的上一个位置
4、当cur == N的时候，dp[cur][rest] =walkCache(N, N - 1, rest - 1, P,dp); 我们dp当前位置依赖于N-1位置，和rest - 1位置
5、当cur在任意中间位置时。dp[cur][rest] = walkCache(N, cur + 1, rest - 1, P,dp) + walkCache(N, cur - 1, rest - 1, P, dp); dp的当前位置依赖于dp的cur+1和rest-1位置加上dp的cur-1和rest-1的位置
那么我们可以得到我们的DP表为：
```text
0 1 2 3 4 5 K 坐标
0 x x x x x x
1 0 0 1 0 3 0
2 0 1 0 3 0 9
3 1 0 2 0 6 0
4 0 1 0 3 0 10
5 0 0 1 0 5 0
6 0 0 0 1 0 5
7 0 0 0 0 1 0
cur
坐
标
```
==所以任何的动态规划，都可以由暴力递归改出来。也就是所任意的动态规划都来自于某个暴力递归。反之任何暴力递归不一定能改成动态规划，加入某暴力递归并没有重复计算，没有缓存的必要==
==动态规划实质就是把参数组合完成结构化的缓存==
```Java
package class12;
public class Code01_RobotWalk {
public static int ways1(int N, int M, int K, int P) {
// 参数无效直接返回0
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
// 总共N个位置，从M点出发，还剩K步可以走，返回最终能达到P的方法数
return walk(N, M, K, P);
}
// N : 位置为1 ~ N，固定参数
// cur : 当前在cur位置，可变参数
// rest : 还剩res步没有走，可变参数
// P : 最终目标位置是P，固定参数
// 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
public static int walk(int N, int cur, int rest, int P) {
// 如果没有剩余步数了，当前的cur位置就是最后的位置
// 如果最后的位置停在P上，那么之前做的移动是有效的
// 如果最后的位置没在P上，那么之前做的移动是无效的
if (rest == 0) {
return cur == P ? 1 : 0;
}
// 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
// 后续的过程就是，来到2位置上，还剩rest-1步要走
if (cur == 1) {
return walk(N, 2, rest - 1, P);
}
// 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
// 后续的过程就是，来到N-1位置上，还剩rest-1步要走
if (cur == N) {
return walk(N, N - 1, rest - 1, P);
}
// 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
// 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
// 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
// 走向左、走向右是截然不同的方法，所以总方法数要都算上
return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
}
public static int waysCache(int N, int M, int K, int P) {
// 参数无效直接返回0
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
// 我们准备一张缓存的dp表
// 由于我们的cur范围是1~N，我们准备N+1。
// rest范围在1~K。我们准备K+1。
// 目的是把我们的可能结果都能装得下
int[][] dp = new int[N+1][K+1];
// 设置这张表的初始值都为-1，代表都还没用过
for(int row = 0; row <= N; row++) {
for(int col = 0; col <= K; col++) {
dp[row][col] = -1;
}
}
return walkCache(N, M, K, P,dp);
}
// HashMap<String, Integer> (19,100) "19_100"
// 我想把所有cur和rest的组合，返回的结果，加入到缓存里
public static int walkCache(int N, int cur, int rest, int P, int[][] dp) {
// 当前场景已经计算过，不要再暴力展开，直接从缓存中拿
if(dp[cur][rest] != -1) {
return dp[cur][rest];
}
if (rest == 0) {
// 先加缓存
dp[cur][rest] = cur == P ? 1 : 0;
return dp[cur][rest];
}
if (cur == 1) {
// 先加缓存
dp[cur][rest] = walkCache(N, 2, rest - 1, P, dp);
return dp[cur][rest];
}
if (cur == N) {
// 先加缓存
dp[cur][rest] =walkCache(N, N - 1, rest - 1, P,dp);
return dp[cur][rest];
}
// 先加缓存
dp[cur][rest] = walkCache(N, cur + 1, rest - 1, P,dp)
+ walkCache(N, cur - 1, rest - 1, P, dp);
return dp[cur][rest];
}
public static int ways2(int N, int M, int K, int P) {
// 参数无效直接返回0
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[][] dp = new int[K + 1][N + 1];
dp[0][P] = 1;
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= N; j++) {
if (j == 1) {
dp[i][j] = dp[i - 1][2];
} else if (j == N) {
dp[i][j] = dp[i - 1][N - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
}
}
}
return dp[K][M];
}
public static int ways3(int N, int M, int K, int P) {
// 参数无效直接返回0
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[] dp = new int[N + 1];
dp[P] = 1;
for (int i = 1; i <= K; i++) {
int leftUp = dp[1];// 左上角的值
for (int j = 1; j <= N; j++) {
int tmp = dp[j];
if (j == 1) {
dp[j] = dp[j + 1];
} else if (j == N) {
dp[j] = leftUp;
} else {
dp[j] = leftUp + dp[j + 1];
}
leftUp = tmp;
}
}
return dp[M];
}
// ways4是你的方法
public static int ways4(int N, int M, int K, int P) {
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
return process(N, 0, P, M, K);
}
// 一共N个位置，从M点出发，一共只有K步。返回走到位置j，剩余步数为i的方法数
public static int process(int N, int i, int j, int M, int K) {
if (i == K) {
return j == M ? 1 : 0;
}
if (j == 1) {
return process(N, i + 1, j + 1, M, K);
}
if (j == N) {
return process(N, i + 1, j - 1, M, K);
}
return process(N, i + 1, j + 1, M, K) + process(N, i + 1, j - 1, M, K);
}
// ways5是你的方法的dp优化
public static int ways5(int N, int M, int K, int P) {
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[][] dp = new int[K + 1][N + 1];
dp[K][M] = 1;
for (int i = K - 1; i >= 0; i--) {
for (int j = 1; j <= N; j++) {
if (j == 1) {
dp[i][j] = dp[i + 1][j + 1];
} else if (j == N) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j - 1];
}
}
}
return dp[0][P];
}
public static void main(String[] args) {
System.out.println(ways1(7, 4, 9, 5));
System.out.println(ways2(7, 4, 9, 5));
System.out.println(ways3(7, 4, 9, 5));
System.out.println(ways4(7, 4, 9, 5));
System.out.println(ways5(7, 4, 9, 5));
}
}
```
<h2 id='12'>1.2 例二：背包问题改动态规划</h2>
> 暴力递归过程各种，我们如何组织我们的决策过程。实质就是动态规划的状态转移
```Java
package class12;
public class Code03_Knapsack {
public static int getMaxValue(int[] w, int[] v, int bag) {
// 主函数需要0 bag的返回值
return process(w, v, 0, 0, bag);
}
// index... 最大价值
public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
if (alreadyW > bag) {
return -1;
}
// 重量没超
if (index == w.length) {
return 0;
}
int p1 = process(w, v, index + 1, alreadyW, bag);
int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
int p2 = -1;
if (p2next != -1) {
p2 = v[index] + p2next;
}
return Math.max(p1, p2);
}
public static int maxValue(int[] w, int[] v, int bag) {
return process(w, v, 0, bag);
}
// 只剩下rest的空间了，
// index...货物自由选择，但是不要超过rest的空间
// 返回能够获得的最大价值
public static int process(int[] w, int[] v, int index, int rest) {
if (rest < 0) { // base case 1
return -1;
}
// rest >=0
if (index == w.length) { // base case 2
return 0;
}
// 有货也有空间
int p1 = process(w, v, index + 1, rest);
int p2 = -1;
int p2Next = process(w, v, index + 1, rest - w[index]);
if(p2Next!=-1) {
p2 = v[index] + p2Next;
}
return Math.max(p1, p2);
}
// dpWay就是把上述的暴力递归改为动态规划
public static int dpWay(int[] w, int[] v, int bag) {
int N = w.length;
// 准备一张dp表，行号为我们的重量范围。列为我们的价值范围
int[][] dp = new int[N + 1][bag + 1];
// 由于暴力递归中index==w.length的时候，总是返回0。所以：
// dp[N][...] = 0。整形数组初始化为0，无需处理
// 由于N行已经初始化为0，我们从N-1开始。填我们的dp表
for (int index = N - 1; index >= 0; index--) {
// 剩余空间从0开始，一直填写到bag
for (int rest = 0; rest <= bag; rest++) { // rest < 0
// 通过正常位置的递归处理
// 我们转而填写dp表格,注释位置是正常递归处理
// int p1 = process(w, v, index + 1, rest);
// int p2 = -1;
// int p2Next = process(w, v, index + 1, rest - w[index]);
// if(p2Next!=-1) {
// p2 = v[index] + p2Next;
// }
// return Math.max(p1, p2);
// 所以我们p1等于dp表的下一层向上一层返回
int p1 = dp[index+1][rest];
int p2 = -1;
// rest - w[index] 不越界
if(rest - w[index] >= 0) {
p2 = v[index] + dp[index + 1][rest - w[index]];
}
// p1和p2取最大值
dp[index][rest] = Math.max(p1, p2);
}
}
// 最终返回dp表的0，bag位置，就是我们暴力递归的主函数调用
return dp[0][bag];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7 };
int[] values = { 5, 6, 3, 19 };
int bag = 11;
System.out.println(maxValue(weights, values, bag));
System.out.println(dpWay(weights, values, bag));
}
}
```
<h2 id='13'>1.3 动态规划解题思路</h2>
1、拿到题目先找到某一个暴力递归的写法（尝试）
2、分析我们的暴力递归，是否存在重复解。没有重复解的递归没必要改动态规划
3、把暴力递归中的可变参数，做成缓存结构，不讲究组织。即没算过加入缓存结构，算过的直接拿缓存，就是记忆化搜索
4、如果把缓存结构做精细化组织，就是我们经典的动态规划
5、以背包问题举例，我们每一个重量有要和不要两个选择，且都要递归展开。那么我们的递归时间复杂度尾O(2^N)。而记忆化搜索，根据可变参数得到的长为N价值为W的二维表，那么我们的时间复杂度为O(N*bag)。如果递归过程中状态转移有化简继续优化的可能，例如枚举。那么经典动态规划可以继续优化，否则记忆化搜索和动态规划的时间复杂度是一样的
<h3 id='131'>1.3.1 凑货币问题（重要）</h3>
> 该题是对动态规划完整优化路径的演示
有一个表示货币面值的数组arr，每种面值的货币可以使用任意多张。arr数组元素为正数，且无重复值。例如[7,3,100,50]这是四种面值的货币。
问：给定一个特定金额Sum，我们用货币面值数组有多少种方法，可以凑出该面值。例如P=1000,用这是四种面值有多少种可能凑出1000
> ways1为暴力递归的解题思路及实现
> ways2为暴力递归改记忆化搜索的版本
> ways3为记忆化搜索版本改动态规划的版本
```Java
package class12;
public class Code09_CoinsWay {
// arr中都是正数且无重复值，返回组成aim的方法数，暴力递归
public static int ways1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
return process1(arr, 0, aim);
}
public static int process1(int[] arr, int index, int rest) {
// base case
// 当在面值数组的arr.length，此时越界，没有货币可以选择。
// 如果当前目标金额就是0，那么存在一种方法，如果目标金额不为0，返回0中方法
if(index == arr.length) {
return rest == 0 ? 1 : 0 ;
}
// 普遍位置
int ways = 0;
// 从0号位置开始枚举，选择0张，1张，2张等
// 条件是张数乘以选择的面值，不超过木匾面值rest
for(int zhang = 0; zhang * arr[index] <= rest ;zhang++) {
// 方法数加上除去当前选择后所剩面额到下一位置的选择数，递归
ways += process1(arr, index + 1, rest - (zhang * arr[index]) );
}
return ways;
}
// ways1暴力递归，改为记忆化搜索。ways2为记忆化搜索版本
public static int ways2(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
// 缓存结构，且只和index和rest有关，跟arr无关
int[][] dp = new int[arr.length+1][aim+1];
// 一开始所有的过程，都没有计算呢，dp二维表初始化为-1
// dp[..][..] = -1
for(int i = 0 ; i < dp.length; i++) {
for(int j = 0 ; j < dp[0].length; j++) {
dp[i][j] = -1;
}
}
// 缓存结构向下传递
return process2(arr, 0, aim , dp);
}
// 如果index和rest的参数组合，是没算过的，dp[index][rest] == -1
// 如果index和rest的参数组合，是算过的，dp[index][rest] > - 1
public static int process2(int[] arr,
int index, int rest,
int[][] dp) {
if(dp[index][rest] != -1) {
return dp[index][rest];
}
if(index == arr.length) {
dp[index][rest] = rest == 0 ? 1 :0;
return dp[index][rest];
}
int ways = 0;
for(int zhang = 0; zhang * arr[index] <= rest ;zhang++) {
// 返回之前加入缓存
ways += process2(arr, index + 1, rest - (zhang * arr[index]) , dp );
}
// 返回之前加入缓存
dp[index][rest] = ways;
return ways;
}
// 记忆化搜索改造为动态规划版本，ways3。
// 如果没有枚举行为，该动态该规划为自顶向下的动态规划和记忆化搜索等效，但这题存在枚举行为。
public static int ways3(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
// dp表
int[][] dp = new int[N + 1][aim + 1];
// 根据递归方法，N为arr的越界位置，但是我们的dp表定义的是N+1。
// N位置，如果aim为0，则dp[N][0] = 1;
dp[N][0] = 1;// dp[N][1...aim] = 0;
// 每个位置依赖自己下面的位置，那么我们从下往上循环
for(int index = N - 1; index >= 0; index--) {
// rest从左往右
for(int rest = 0; rest <= aim; rest++) {
int ways = 0;
for(int zhang = 0; zhang * arr[index] <= rest ;zhang++) {
ways += dp[index + 1] [rest - (zhang * arr[index])];
}
dp[index][rest] = ways;
}
}
// 最终我们需要[0,aim]位置的解
return dp[0][aim];
}
// 由于存在枚举行为，我们可以进一步优化我们的动态规划。ways4是优化的动态规划
// 根据枚举，用具体化例子来找出规律，省掉枚举
public static int ways4(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;// dp[N][1...aim] = 0;
for(int index = N - 1; index >= 0; index--) {
for(int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index+1][rest];
if(rest - arr[index] >= 0) {
dp[index][rest] += dp[index][rest - arr[index]];
}
}
}
return dp[0][aim];
}
public static void main(String[] args) {
int[] arr = { 5, 10,50,100 };
int sum = 1000;
System.out.println(ways1(arr, sum));
System.out.println(ways2(arr, sum));
System.out.println(ways3(arr, sum));
System.out.println(ways4(arr, sum));
}
}
```
<h3 id='132'>1.3.2 贴纸问题</h3>
给定一个字符串str，给定一个字符串类型的数组arr。arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。
返回需要至少多少张贴纸可以完成这个任务。
例如：str="babac"，arr={"ba","c","abcd"}
至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符串单独剪开，含有2个a，2个b，1个c。是可以拼出str的，所以返回2。
> 思路1 minStickers1：由于任何贴纸都可以剪切的很碎，跟贴纸的顺序没关系。那么目标str我们先进行排序，那么也不会有影响。babac排序为aabbc，我们再去选择贴纸，str被贴纸贴好后，剩下的接着排序，再选择......
> 由于我们的可变参数，只有一个目标字符串。但是目标字符串的可能性太多，没办法精细化动态规划。傻缓存的暴力递归已经是最优解了。所以只有一个可变参数，又存在重复解，那么傻缓存就是最优解。
> 思路2 minStickers2，我们每一张贴纸枚举所有可能的张数，后续过程不再考虑这张贴纸。但是方法一会好一点，因为只有一个可变参数。而方法二有两个可变参数，我们在设计递归的时候，尽量少的使用可变参数，这样我们缓存结构的命中率会提升
```Java
package class12;
import java.util.Arrays;
import java.util.HashMap;
public class Code02_StickersToSpellWord {
// 暴力递归加缓存dp
public static int minStickers1(String[] stickers, String target) {
int n = stickers.length;
// stickers -> [26] [26] [26]
// 表示把每张贴纸转化为26个字母的词频数组
int[][] map = new int[n][26];
// 把每一张贴纸转化的字母26个字母有多少个
for (int i = 0; i < n; i++) {
char[] str = stickers[i].toCharArray();
for (char c : str) {
map[i][c - 'a']++;
}
}
HashMap<String, Integer> dp = new HashMap<>();
dp.put("", 0);
return process1(dp, map, target);
}
// dp 傻缓存，如果rest已经算过了，直接返回dp中的值
// rest 剩余的目标
// 0..N每一个字符串所含字符的词频统计
// 返回值是-1，map 中的贴纸 怎么都无法rest
public static int process1(
HashMap<String, Integer> dp,
int[][] map,
String rest) {
if (dp.containsKey(rest)) {
return dp.get(rest);
}
// 以下就是正式的递归调用过程
int ans = Integer.MAX_VALUE; // ans -> 搞定rest，使用的最少的贴纸数量
int n = map.length; // N种贴纸
int[] tmap = new int[26]; // tmap 去替代 rest
// 把目标target剩余的rest进行词频统计
char[] target = rest.toCharArray();
for (char c : target) {
tmap[c - 'a']++;
}
// map表示所有贴纸的词频信息，tmap表示目标字符串的词频信息
// 用map去覆盖tmap
for (int i = 0; i < n; i++) {
// 枚举当前第一张贴纸是谁？
// 第一张贴纸必须包含当前目标字符串的首字母。和所有贴纸去选等效
// 目的是让当前贴纸的元素有在目标字符串的对应个，否则试过之后仍然是原始串，栈会溢出
if (map[i][target[0] - 'a'] == 0) {
continue;
}
StringBuilder sb = new StringBuilder();
// i 贴纸， j 枚举a~z字符
for (int j = 0; j < 26; j++) { //
if (tmap[j] > 0) { // j这个字符是target需要的
for (int k = 0; k < Math.max(0, tmap[j] - map[i][j]); k++) {
// 添加剩余
sb.append((char) ('a' + j));
}
}
}
// sb -> i 此时s就是当前贴纸搞定之后剩余的
String s = sb.toString();
// tmp是后续方案需要的贴纸数
int tmp = process1(dp, map, s);
// 如果-1表示贴纸怎么都无法覆盖目标字符串
if (tmp != -1) {
// 不是-1，最终返回当前后续贴纸数，加上当前贴纸数与ans的最小值
ans = Math.min(ans, 1 + tmp);
}
}
// 经过上述循环，ans仍然系统最大，表示怎么都无法覆盖rest，返回-1
dp.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
return dp.get(rest);
}
public static int minStickers2(String[] stickers, String target) {
int n = stickers.length;
int[][] map = new int[n][26];
for (int i = 0; i < n; i++) {
char[] str = stickers[i].toCharArray();
for (char c : str) {
map[i][c - 'a']++;
}
}
char[] str = target.toCharArray();
int[] tmap = new int[26];
for (char c : str) {
tmap[c - 'a']++;
}
HashMap<String, Integer> dp = new HashMap<>();
int ans = process2(map, 0, tmap, dp);
return ans;
}
public static int process2(int[][] map, int i, int[] tmap, HashMap<String, Integer> dp) {
StringBuilder keyBuilder = new StringBuilder();
keyBuilder.append(i + "_");
for (int asc = 0; asc < 26; asc++) {
if (tmap[asc] != 0) {
keyBuilder.append((char) (asc + 'a') + "_" + tmap[asc] + "_");
}
}
String key = keyBuilder.toString();
if (dp.containsKey(key)) {
return dp.get(key);
}
boolean finish = true;
for (int asc = 0; asc < 26; asc++) {
if (tmap[asc] != 0) {
finish = false;
break;
}
}
if (finish) {
dp.put(key, 0);
return 0;
}
if (i == map.length) {
dp.put(key, -1);
return -1;
}
int maxZhang = 0;
for (int asc = 0; asc < 26; asc++) {
if (map[i][asc] != 0 && tmap[asc] != 0) {
maxZhang = Math.max(maxZhang, (tmap[asc] / map[i][asc]) + (tmap[asc] % map[i][asc] == 0 ? 0 : 1));
}
}
int[] backup = Arrays.copyOf(tmap, tmap.length);
int min = Integer.MAX_VALUE;
int next = process2(map, i + 1, tmap, dp);
tmap = Arrays.copyOf(backup, backup.length);
if (next != -1) {
min = next;
}
for (int zhang = 1; zhang <= maxZhang; zhang++) {
for (int asc = 0; asc < 26; asc++) {
tmap[asc] = Math.max(0, tmap[asc] - (map[i][asc] * zhang));
}
next = process2(map, i + 1, tmap, dp);
tmap = Arrays.copyOf(backup, backup.length);
if (next != -1) {
min = Math.min(min, zhang + next);
}
}
int ans = min == Integer.MAX_VALUE ? -1 : min;
dp.put(key, ans);
return ans;
}
public static void main(String[] args) {
String[] arr = {"aaaa","bbaa","ccddd"};
String str = "abcccccdddddbbbaaaaa";
System.out.println(minStickers1(arr, str));
System.out.println(minStickers2(arr, str));
}
}
```
<h2 id='14'>1.4 什么暴力递归可以继续优化？</h2>
1、有重复调用同一个子问题的解，这种递归可以优化
2、如果每一个子问题都是不同的解，无法优化也不用优化
<h2 id='15'>1.5 暴力地柜和动态规划的关系</h2>
1、某个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
2、任何动态规划问题，都一定对应着某一个有解的重复调用的暴力递归
3、不是所有的暴力递归，都一定对应着动态规划
<h2 id='16'>1.6 面试题中和动态规划的关系</h2>
1、解决一个问题，可能有很多尝试方法
2、可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式
3、一个问题，可能有若干种动态规划的解法
<h2 id='17'>1.7 如何找到某个问题的动态规划方式？</h2>
1、设计暴力递归：重要原则+4中常见尝试模型！重点
2、分析有没有重复解：套路解决
3、用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
4、看看能否继续优化：套路解决
<h2 id='18'>1.8 面试中设计暴力递归过程的原则</h2>
==怎么猜是不对的？==
1、每一个可变参数，一定不要比int类型更加复杂
> 比如可变参数是int a和int b 那么我们的缓存结构可以是a*b的二维数组。大小取决于a和b的范围
> 但是如果我们的可变参数是一个数组，int[] a。那么如果过多，我们不太容易设计那么大的缓存结构。如果只有一个这种可变参数就是原则2
==不管什么问题，我们在脑海中想象可变参数就不会突破整形范围==
2、原则1可以违反，让类型突破到一维线性结构，那必须是唯一可变参数。例如上述贴纸问题
3、如果发现原则1被违反，但没违反原则2。只需要做到记忆化搜索就是最优解
3、可变参数个数，能少则少
<h2 id='19'>1.9 笔试面试过程中怎么设计暴力递归？</h2>
1、一定逼自己找到不违反1.8原则情况下的暴力尝试！
2、如果你找到暴力尝试，不符合原则，马上舍弃，找新的！
3、如果某个题目突破了设计原则，一定极难极难，面试中出现的概率低于5%
<h2 id='110'>1.10 常见的4种尝试模型</h2>
> 每一个模型背后都有很多题目
<h3 id='1101'>1.10.1 从左往右的尝试模型</h3>
> 例如背包问题
<h3 id='1102'>1.10.2 范围上的尝试模型</h3>
> 例如纸牌博弈问题
<h3 id='1103'>1.10.3 多样本位置全对应的尝试模型</h3>
<h4 id='11031'>1.10.3.1 两个字符串的最长公共子序列问题</h4>
> 例如“ab1cd2ef345gh”和“opq123rs4tx5yz”的最长公共子序列为“12345”。即在两个字符串所有相等的子序列里最长的。所以返回子序列的长度5
> 假如"a123bc"和"12dea3fz"两个字符串，我们把这两个样本的下标一个作为行，一个作为列。观察这样的结构所表示的意义。dp表这样设计就是str1从0到i位置，str2从0到j位置，两个位置的最长公共子序列。
> dp[i][j] 表示的含义是，str1字符串在i位置，
str2在j位置，两个最长公共子序列多长。
那么str1和str2的最长公共子序列，就是dp[str1.length][str2.length]
> 对于任何位置dp[i][j]:
> 1. 如果str1的i位置和str2的j位置的最长公共子序列跟str1的i位置字符和str2的j位置字符无关，那么此时的最长公共子序列长度就是dp[i-1][j-1]
> 2. 此时与str1的i位置结尾的字符有关系，和str2的j位置结尾的字符没关系。此时跟str2的j位置没关系，最长公共子序列式dp[i][j-1]
> 3. 此时与str1的i位置结尾的字符没关系，和str2的j位置结尾的字符有关系。此时跟str1的j位置没关系，最长公共子序列式dp[i-1][j]
> 4. 此时即与str1的i字符结尾，有关系。又与str2的j位置结尾，有关系。只有str1[i]==str2[j]才有可能存在这种情况，且为dp[i-1][j-1] + 1
```text
0 1 2 3 4 5 6 7 str2
0 0 0 0 0 1 1 1 1
1 0
2 1
3 1
4 1
5 1
str1
```
```Java
package class12;
public class Code05_PalindromeSubsequence {
public static int lcse(char[] str1, char[] str2) {
int[][] dp = new int[str1.length][str2.length];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
// 填第0列的所有值
// 一旦st1r的i位置某个字符等于str2的0位置，那么之后都是1
for (int i = 1; i < str1.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
}
// 填第0行的所有值
// 一旦str2的j位置某个字符等于str1的0位置，那么之后都是1
for (int j = 1; j < str2.length; j++) {
dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
}
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
// dp[i - 1][j]表示可能性2
// dp[i][j - 1] 表示可能性3
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[str1.length - 1][str2.length - 1];
}
public static void main(String[] args) {
}
}
```
<h3 id='1104'>1.10.4 寻找业务限制的尝试模型</h3>
> 四种模型中最难的一种，暂时只看process方法，process更改为动态规划的dp方法。后面会展开说明其他方法，
例题：给定一个数组，代表每个人喝完咖啡准备刷杯子的时间，只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯。每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发。返回让所有咖啡杯变干净的最早完成时间。三个参数：int[]arr , int a , int b（京东）
```Java
package class12;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
// 题目
// 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
// 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
// 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
// 每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
// 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
// 四个参数：arr, n, a, b
// 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
public class Code06_Coffee {
// 方法一：暴力尝试方法
public static int minTime1(int[] arr, int n, int a, int b) {
int[] times = new int[arr.length];
int[] drink = new int[n];
return forceMake(arr, times, 0, drink, n, a, b);
}
// 方法一，每个人暴力尝试用每一个咖啡机给自己做咖啡
public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
if (kth == n) {
int[] drinkSorted = Arrays.copyOf(drink, kth);
Arrays.sort(drinkSorted);
return forceWash(drinkSorted, a, b, 0, 0, 0);
}
int time = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
int work = arr[i];
int pre = times[i];
drink[kth] = pre + work;
times[i] = pre + work;
time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));
drink[kth] = 0;
times[i] = pre;
}
return time;
}
// 方法一，暴力尝试洗咖啡杯的方式
public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
if (index == drinks.length) {
return time;
}
// 选择一：当前index号咖啡杯，选择用洗咖啡机刷干净
int wash = Math.max(drinks[index], washLine) + a;
int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));
// 选择二：当前index号咖啡杯，选择自然挥发
int dry = drinks[index] + b;
int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time));
return Math.min(ans1, ans2);
}
// 方法二：稍微好一点的解法
public static class Machine {
public int timePoint;
public int workTime;
public Machine(int t, int w) {
timePoint = t;
workTime = w;
}
}
public static class MachineComparator implements Comparator<Machine> {
@Override
public int compare(Machine o1, Machine o2) {
return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
}
}
// 方法二，每个人暴力尝试用每一个咖啡机给自己做咖啡，优化成贪心
public static int minTime2(int[] arr, int n, int a, int b) {
PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
for (int i = 0; i < arr.length; i++) {
heap.add(new Machine(0, arr[i]));
}
int[] drinks = new int[n];
for (int i = 0; i < n; i++) {
Machine cur = heap.poll();
cur.timePoint += cur.workTime;
drinks[i] = cur.timePoint;
heap.add(cur);
}