368. Maximum divisible subset dynamic programming

The original title is ：

Power button

Ideas ： Dynamic programming + Memory search

inspiration ：

 

Code ：

package  Algorithm . Dynamic programming .leetcode;

import java.util.*;

/**
 *  Union checking set 
 */
public class leetcode368 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,6,12,24};
        List<Integer> list = largestDivisibleSubset(nums);

    }

    public static List<Integer> largestDivisibleSubset(int[] nums) {
        // Prioritize 
        Arrays.sort(nums);
        Map<String,List<Integer>> map = new HashMap<>();
        // Dynamic planning results 
        List<Integer> list = getList(nums,nums.length-1,nums.length-2,map);
        // Patch    Don't think about it 
        if(nums[nums.length-1] % nums[nums.length-2] == 0){
            list.add(nums[nums.length-1]);
        }
        // return 
        return list;
    }

    /**
     *
     * @param nums
     * @param i   Big   Count 
     *        j   Small trees 
     * @return
     */
    private static List<Integer> getList(int[] nums, int i, int j, Map<String,List<Integer>> map) {
        // That means it's gone 
        if (j == -1||i==0) {
            return new ArrayList<>();
        }
        // Memory search 
        StringBuilder key = new StringBuilder();
        key.append(i);
        key.append(j);
        if (map.containsKey(key.toString())) {
            List<Integer> old = new ArrayList<>();
            old.addAll(map.get(key.toString()));
            return old;
        }
        List<Integer> one = new ArrayList<>();
        List<Integer> two = new ArrayList<>();
        // If you can get rid of it, keep looking , Otherwise, the next number 
        if(nums[i] % nums[j] == 0){
            one = getList(nums,j,j-1,map);
            one.add(nums[j]);
        }
        two = getList(nums,i,j-1,map);
        one =  one.size()> two.size()? one:two;
        List<Integer> newList = new ArrayList<>();
        newList.addAll(one);
        // Memory search 
        map.put(key.toString(),newList);
        return one;
    }
}