leetcode

题意：

给一列数，找出其中最长的一个子序列。使序列中所有的数字两两可整除。

分析：

随便举个例子分析dp[ i ]

1  2  3  9  16  32

比如截止9这时候最长的是139，但是到最后最长的是 1  2  16  32

所以，说明dp是会更新，且更新的依据遍布1到i-1

所以就是：对于dp[ i ]    , 遍历1到 i-1。 当nums[ i ]是nums[ j ]倍数的时候，找到最大的dp [ j ]  ，dp[i]比它大1

反思：动态规划就是要找到dp[ j ]和它的关系。

但是找到最大的dp还不够，因为返回的是具体的数组。

我们只需要查找满足条件的（这样可能找到不属于最大序列却仍然满足整除条件的）。所以可以利用找到的最大dp值--，来限制。

public class Solution {     public List<Integer> largestDivisibleSubset(int[] nums) {         List<Integer> list = new ArrayList<>();         if(nums.length==0)             return list;         int[] dp = new int[nums.length];         int max = 0;         int maxi = 0;         dp[0] = 1;         //1 动态规划找到每个数能含有的最多的满足条件的元素的个数         Arrays.sort(nums);         for(int i=1; i<nums.length; i++){             for(int j=0; j<i; j++){                 if(nums[i]%nums[j]==0){                     dp[i] = Math.max(dp[i],dp[j] + 1);                 }             }             if(dp[i] > max){  //找最大的dp[i]                 max = dp[i];                 maxi = i;             }         }         //2 根据最大的dp的值和对应位置的数组值，找整个最长序列的所有元素         int s = dp[maxi];         for (int i = maxi; i >= 0; i--){             if (nums[maxi] % nums[i] == 0 && dp[i] == s){                 list.add(nums[i]);                 s--;                        //避免找到其他序列的（dp相同的），每个dp值只找一个             }         }         return list;     } }