Algorithm：1048. 最长字符串链
Review： 一步一步的解决打家劫舍3问题
Tip/Tech： 二分搜索
Share：机器中的达尔文
Algorithm
1048. 最长字符串链
https://leetcode-cn.com/problems/longest-string-chain/
这里其实还是很简答的， 你要说这是动态规划，那也没啥毛病。但是估计是最简单动态规划了。首先我们要知道，最长的单词链，单词里的字母的数量一定是越到后面是越多的。
其次，我们还要知道，词链的后一个单词和他的前一个单词的关系就是多了一个字母，然后添加到了任意位置，这样我们根据单词的字母的数量进行分桶。
一个桶里面放字母数量想同的单词。
接着进行遍历比较，把后一个桶里的全部的单词和前一个桶里的单词进行校验，获取可以作为词链的最大的当前的词链值。接下来我们来看看代码实现，代码中有注解，希望你可以看明白。
class Solution {
public int longestStrChain(String[] words) {
ArrayList<ArrayList<String>> buckets = new ArrayList<>(16);// 初始化桶，大小肯定是设置为16，肯定够用，没办法，题目说了。for (int i = 0; i < 16; ++i) {
buckets.add(new ArrayList<>());}// 分桶咯。一个桶放字母相同的相同的单词for (String temp : words) {
ArrayList<String> tempList = buckets.get(temp.length() - 1);tempList.add(temp);}// 哈希表存放每个单词可以达到的最大的词链长度。Map<String, Integer> mapInteger = new HashMap<>();int ans = 1;// 先设置最小的字母的数量的for (ArrayList<String> item : buckets) {
if (item.size() > 0) {
for (String itemString : item) {
mapInteger.put(itemString, 1);}break;}}
// 遍历所有的桶，后一个和前一个的桶进行比较。for (int i = 1, len = buckets.size(); i < len; ++i) {
ArrayList<String> tempListLess = buckets.get(i - 1);ArrayList<String> tempListMore = buckets.get(i);for (String itemMore : tempListMore) {
for (String itemLess : tempListLess) {
// 如果满足词链的规则，那么就把那个前一个词链的长度最大长度加一个。if (isAfterWord(itemLess, itemMore)) {
int count = mapInteger.getOrDefault(itemLess, 1);mapInteger.put(itemMore, count+1);ans = Math.max(ans, count + 1);}}}}return ans;}
// 只有一个不一样，超过一个就不符合词链的规则了。private boolean isAfterWord(String first, String second) {
HashSet<Character> set = new HashSet<>();int count = 0;int index1 = 0;int index2 = 0;int lenFirst = first.length();while (index1 < lenFirst) {
if (first.charAt(index1) == second.charAt(index2)) {
index1++;index2++;} else {
if (count < 1) {
count++;index2++;} else {
return false;}}}return true;}
}
Reviewm
一步一步的解决打家劫舍3问题
https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem
这篇文章对应的是Leetcode的第337. 打家劫舍 III，这个作者无疑是个很会分享知识的人，他详细的一步一步地的讲述了是如何解决这个问题的。
解释的非常不错。
第一：
直接就是递归思想，你可以把它想成，你要找到当前这个根节最大的收益，然后你可以对你的左右的子节点也这么做。当然，这个也是时间复杂度最高的，对于递归的问题，主要掌握两个条件：终止条件和递归条件。
1 终止条件：要么我们知道答案就不用计算了，要么就是遍历的节点为空。
2 递归条件：首先，两个相连的不能偷，所以，根节点如果投了，那么子节点就不能偷了，你只能去偷子节点的节点，也就是孙子节点。。。
然后保证你的孙子节点就是偷到最大的金钱。
可以来看第一步的代码，这里就直接引用文章的代码了：
public int rob(TreeNode root) {
if (root == null) return 0;int val = 0;// 如果左节点不为空。if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);}// 如果右节点不为空。if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);}// 选个最大的方案return Math.max(val + root.val, rob(root.left) + rob(root.right));
}
时间复杂度较高，直接就是 O ( n ! ) O(n!) O(n!)
第二
优化吧计算过的结果记录下来，然递归的时候不要重复计算，这样就把计算的次数减少了很多，时间复杂度是就是O（n）走两轮完成，我们来看看代码：
if (root == null) return 0;if (map.containsKey(root)) return map.get(root);int val = 0;if (root.left != null) {
val += robSub(root.left.left, map) + robSub(root.left.right, map);} if (root.right != null) {
val += robSub(root.right.left, map) + robSub(root.right.right, map);}val = Math.max(val + root.val, robSub(root.left, map) + robSub(root.right, map));map.put(root, val);return val;
其实能到这一步基本上就是很厉害了，就是空间复杂度有点高，但是现在普遍的内存很高。
第三部
优化空间：
public int rob(TreeNode root) {
int[] res = robSub(root);return Math.max(res[0], res[1]);
}private int[] robSub(TreeNode root) {
if (root == null) return new int[2];int[] left = robSub(root.left);int[] right = robSub(root.right);int[] res = new int[2];res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);res[1] = root.val + left[0] + right[0];return res;
}java
这题很经典啊，同时也有些复杂。
Tip/Tech
基本就是通过二分搜索，完了二分搜索的代码啊嘱咐也很重要的。
Share
https://en.wikipedia.org/wiki/Darwin_among_the_Machines
机器中的达尔文
文章认为机器如果智能到了那个地步，那么就可以完成多个通过创造达尔文这样 的人来进行检查，
秋实还有一个观点就是，其实你需要达尔文，爱因斯坦，牛顿这样的 科学家才有希望完成迭代进化