构造一个集合，每次给集合放入新的点A，都判断集合中其他的点到该点的距离，取最大值为集合内部到新点A的最大距离L。下次再加入新的点A1，如果A和A1连通，则集合到A1的距离为L+1。
由于终点有多个，最后要遍历所有点的最长距离。
其实这道题的思想和Dijkstra算法是一样的。
代码：
class Solution { public: bool canChange(string& s1, string& s2) { int len1 = s1.length(); int len2 = s2.length(); if(len1+1!=len2) return false; int i=0; int j=0; while(j<len2) { if(s1[i]==s2[j]) { ++i; ++j; } else { ++j; if(j-i>1) { return false; } } } return true; } int longestStrChain(vector<string>& words) { int n = words.size(); vector<vector<int>> g(n, vector<int>(n, 0)); sort(words.begin(), words.end(), [](string& w1, string& w2) { return w1.length()<w2.length(); } ); for(int i = 0; i < n; ++i) { for(int j = i+1; j < n; ++j) { if(canChange(words[i], words[j])) { g[i][j] = 1; } } } vector<int> lcnt(n, 1); for(int i=0;i<n;++i) { for(int j=0;j<i;++j) { if(g[j][i]) { int tmp = lcnt[j]+1; lcnt[i] = max(tmp, lcnt[i]); } } } return *max_element(lcnt.begin(), lcnt.end()); } }; 4. 最后一块石头的重量 II题目：
最后一块石头的重量 II(Last Stone Weight II)
地址：
https://leetcode-cn.com/contest/weekly-contest-137/problems/last-stone-weight-ii/
题意：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
思路：
和第一题的题意只有一句差别，就是每次拿石头是「任意」的。问最后能消掉剩余的最小值是多少。
一般最开始可能想到用贪心，但实际上没有这种算法的。
由于石头碎掉之后还能放回去，类似于把石头分成两堆来看。只要依次拿两堆的石头互相粉碎，最后剩下的就是最小整数。
最多有100个石头，每个石头最多300的重量。所以两个集合最大的差值不会超过30000。
用数组构造结果。
在加入第n个石头重量为m时，查找n-1个石头能够组成的两堆石头的差值的绝对值为diff。
该石头两个选择，放入多的堆，则差值更大，为diff+m；
放入小的堆，则差值为|diff-m|。这时更新n个石头能组成的所有重量。
最后输出最后一个石头能组成的最小重量即可。
代码：
class Solution { public: int lastStoneWeightII(vector<int>& stones) { int diff[101][30001]={0}; int sum = 0; int n = stones.size(); for(int i=0;i<n;++i) { sum+=stones[i]; } diff[0][stones[0]] = 1; for(int i=1;i<n;++i) { for(int j=0;j<=sum;++j) { if(diff[i-1][j]) { diff[i][j+stones[i]] = 1; diff[i][abs(j-stones[i])] = 1; } } } for(int i = 0; i <= sum; ++i) { if(diff[n-1][i]) { return i; } } return 0; } };