给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-divisible-subset
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：领取
做题前的思考：假如已经有一个两两倍数关系的序列`2 4 8`,若此时来一个8的倍数x，那么x一定是`8 4 2`的倍数，`2 4 8 x`依然保持了两两倍数关系的序列，到了此处就发现可以大问题转换成字问题，于是联想到动态规划。并且在扩展序列的时候是有序的，所以我们需要给nums排序.
对于已经排序后的nums
设定状态: `dp[i]`: 以nums[i]结尾的序列最大长度
`last[i]`: 在最大序列中 nums[i]的上一个元素在nums出现的下标
状态转移方程：
使用二重循环,对于每一个nums[i]，看他可以接在之前的哪个序列dp[j]上，使得dp[i]最长
`nums[i]%nums[j] == 0`是可以接的条件，`dp[i]<=dp[j]`是使得dp[i]变长的条件
初始状态：`dp[i] = 1 (i:1 - n) `每一个只有自己的序列长度为1
```cpp
for(int i = 0;i<sz;i++){
for(int j = 0;j<i;j++)
if(nums[i]%nums[j] == 0 && dp[i]<=dp[j]){
dp[i] = dp[j]+1;
last[i] = j;
}
```
代码
```cpp
class Solution {
public:
vector largestDivisibleSubset(vector& nums) {
int sz = nums.size(),mx = 0,end = -1;
vector dp(sz,1),last(sz,-1),res;
sort(nums.begin(),nums.end());
for(int i = 0;i<sz;i++){
for(int j = 0;j<i;j++){
if(nums[i]%nums[j] == 0 && dp[i]<=dp[j]){
dp[i] = dp[j]+1;
last[i] = j;
}
}
if(dp[i]>mx){
mx = dp[i];
end = i;
}
}
for(int i = end;i!=-1;i = last[i]){//倒序输出
res.push_back(nums[i]);
}
return res;
}
};
```
可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解黑白圆盘一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解：可以用一个相机即可
LeetCode题解圆上任取三点构成锐角三角形的概率来自字节跳动的一道几何题题解：1/4
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈