求背包问题的方案

算法思想：

1. 记忆化存储最优解的转换过程
2. 逆推得到最优解

#

368. 最大整除子集 (opens new window)

求最优方案

需要保存中间状态

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int[] f = new int[n];
        Arrays.fill(f, 1);
        int[] st = new int[n];
        Arrays.fill(st, -1);

        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j > i; j--) {
                if (nums[j] % nums[i] == 0) {
                    if (f[j] < f[i] + 1) {
                        f[j] = f[i] + 1;
                        st[j] = i;
                    }
                }
            }
        }
        int max = Arrays.stream(f).max().getAsInt();
        int p = -1;
        for (int i = 0; i < n; i++) {
            if (max == f[i]) {
                p = i;
                break;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = max - 1; p != -1 && i >= 0; i--) {
            res.add(nums[p]);
            p = st[p];
        }
        return res;
    }
}