題目網址：https://leetcode.cn/problems/largest-divisible-subset/

題意：給一無重覆正整數組成的集合 nums, 找出並返回其中最大的整除 subset answer, 使得其中每一個 pair (answer[i], answer[j]) 都應當滿足：

  • answer[i] % answer[j] == 0 或
  • answer[j] % answer[i] == 0

如果存在多個 subset, 則返回其中一個即可。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i]：在 nums 為升序的前提下, 代表 nums[1:i] 中以 nums[i] 為結尾的最大整除 subset 之長度
  • prev[i]：代表 nums[i] 是由哪一個 idx 的狀態轉移過來的, 以便回溯找出整個 subset

2. 得到轉移方程：

  • 若 nums[i] % nums[j] == 0：則 dp[i] = max(dp[i], dp[j] + 1), 其中 1 ≤ j < i

3. 初始化：

  • dp[0]：當沒有元素時, 最大整除 subset 之長度為 0
  • dp[i]：至少一個元素時, 以 nums[i] 為結尾的最大整除 subset 之長度最小為 1, 其中 1 ≤ i ≤ n
  • prev[1]：為了讓 idx 不斷往前回溯, 進而找出整個 subset。必須設一個終止條件, 將 prev[1] 設為一個不可能會出現的數（由於 prev[i] 存的是 idx, 故設為越界的 idx）
    ➔ prev[1] = -1
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        const int n = nums.size();
        vector<int> dp(n + 1, 1);
        vector<int> prev(n + 1, -1);

        sort(nums.begin(), nums.end());

        nums.emplace(nums.begin(), 0);
        dp[0] = 0;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = max(dp[i], dp[j] + 1);

                    if (dp[i] == dp[j] + 1) {
                        prev[i] = j;
                    }
                }
            }
        }

        // 找出 dp 中最大元素的 idx
        int idx = dp[1];
        for (int i = 2; i <= n; ++i) {
            if (dp[i] > dp[idx]) {
                idx = i;
            }
        }

        vector<int> res;
        while (idx != -1) {
            res.emplace_back(nums[idx]);
            idx = prev[idx];
        }

        return res;
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n)$ ➔ dp, prev