Jerry银银
超哥的这个课,我看得非常快。因为之前用心、用力学完了极客时间的另外一个算法专栏——大家都懂得。
这阵子刻意练习递归、分治、贪心、回溯、动态规划,在练习这些算法的时候,确实遇到了不少难点,有时候,精神都有点「崩溃」了。想想, 超哥这个课确实帮了不少忙,从中也能感受到超哥的实战经验确实比较丰富。 我就说我从课程领悟到的一些要点:
1. 递归模板 很多人都怕写递归,我也是,递归的思想,其实蛮容易懂的, 但是到切题的时候,就不知道如何下手了。我后来想明白了,就是缺少“模板”感觉。如果一上来按照如下几步开始:
第一步:termination
第二步:process
第三步:drill down
第四步:clear state
然后,再往里面填递归代码,这肯定就容易多了。比如,我按照这个模板,填完代码、优化代码, 代码优化到最后,我自己都觉得是太美了,如下:
``` java
class Solution {
private int min = Integer.MAX_VALUE;
public int minimumTotal(List<List<Integer>> triangle) {
dfs(triangle, 0, 0, 0);
return min;
}
private void dfs(List<List<Integer>> triangle, int layer, int pos, int sum) {
if (layer == triangle.size()) {
min = Math.min(sum, min);
return;
}
sum += triangle.get(layer).get(pos);
dfs(triangle, layer + 1, pos, sum);
dfs(triangle, layer + 1, pos + 1, sum);
}
}
```
2. DP
DP做到后面,你就感觉了,有什么感觉呢:看到一个题目,你大概就能感觉出来,它是否可以用DP解决。当觉得可以用DP解决的时候,你再套用最优子结构验证下就可以了。然后就是两步走:
(1) 状态如何定义?
(2) 状态转移方程?
搞定上面两步,剩下的就是转为代码了。
3. 最后就是从超哥这里学到了很多切题的方法,比如: 刻意练习自己不会的类型的题目; 切题可以像打游戏一样等等。
......