序列 DP

题目	难度
368. 最大整除子集	中等
2901. 最长相邻不相等子序列 II	中等

模板

序列 DP + 记录转移关系 倒推答案。

时间复杂度：O(n^2)。

368. 最大整除子集

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution368 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        // f[i] 表示 num[0,i] 最大的整除子集长度
        int[] f = new int[n];
        int[] from = new int[n];
        Arrays.fill(from, -1);
        int maxI = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (f[i] < f[j]) {
                        f[i] = f[j];
                        from[i] = j;
                    }
                }
            }
            f[i]++;
            if (f[i] > f[maxI]) {
                maxI = i;
            }
        }

        List<Integer> ans = new ArrayList<>();
        while (maxI != -1) {
            ans.add(nums[maxI]);
            maxI = from[maxI];
        }
        Collections.reverse(ans);
        return ans;
    }
}

2901. 最长相邻不相等子序列 II

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution2901 {
    // 序列 DP
    // 1、子序列 + 不考虑相邻元素：选或不选。代表：0-1 背包
    // 2、子序列 + 考虑相邻元素：枚举选哪个。代表：LIS
    public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {
        int n = words.length;
        int[] f = new int[n];
        // 记录转移来源
        int[] from = new int[n];
        Arrays.fill(from, -1);

        int maxI = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (f[i] < f[j] && groups[j] != groups[i] && hammingEq1(words[j], words[i])) {
                    f[i] = f[j];
                    from[i] = j;
                }
            }
            // 加一写在这里
            f[i]++;
            if (f[i] > f[maxI]) {
                maxI = i;
            }
        }

        List<String> ans = new ArrayList<>();
        while (maxI != -1) {
            ans.add(words[maxI]);
            maxI = from[maxI];
        }
        Collections.reverse(ans);
        return ans;
    }

    private boolean hammingEq1(String x, String y) {
        if (x.length() != y.length()) {
            return false;
        }
        int cnt = 0;
        for (int i = 0; i < x.length(); i++) {
            if (x.charAt(i) != y.charAt(i)) {
                cnt++;
                if (cnt > 1) return false;
            }
        }
        return cnt == 1;
    }
}

（全文完）