對(duì)于求方案數(shù)的題目，多開一個(gè)數(shù)組來記錄狀態(tài)從何轉(zhuǎn)移而來是最常見的手段。

當(dāng)我們求得所有的狀態(tài)值之后，可以對(duì) f[] 數(shù)組進(jìn)行遍歷，取得具體的最長「整除子集」長度和對(duì)應(yīng)下標(biāo)，然后使用 g[] 數(shù)組進(jìn)行回溯，取得答案。

Java 代碼：

class?Solution?{
????public?List<Integer>?largestDivisibleSubset(int[]?nums)?{
????????Arrays.sort(nums);
????????int?n?=?nums.length;
????????int[]?f?=?new?int[n],?g?=?new?int[n];
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????//?至少包含自身一個(gè)數(shù)，因此起始長度為?1，由自身轉(zhuǎn)移而來
????????????int?len?=?1,?prev?=?i;
????????????for?(int?j?=?0;?j?<?i;?j++)?{
????????????????if?(nums[i]?%?nums[j]?==?0)?{
????????????????????//?如果能接在更長的序列后面，則更新「最大長度」&「從何轉(zhuǎn)移而來」
????????????????????if?(f[j]?+?1?>?len)?{
????????????????????????len?=?f[j]?+?1;
????????????????????????prev?=?j;
????????????????????}
????????????????}
????????????}
????????????//?記錄「最終長度」&「從何轉(zhuǎn)移而來」
????????????f[i]?=?len;?g[i]?=?prev;
????????}
????????//?遍歷所有的?f[i]，取得「最大長度」和「對(duì)應(yīng)下標(biāo)」
????????int?max?=?-1,?idx?=?-1;
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????if?(f[i]?>?max)?{
????????????????idx?=?i;
????????????????max?=?f[i];
????????????}
????????}
????????//?使用?g[]?數(shù)組回溯出具體方案
????????List<Integer>?ans?=?new?ArrayList<>();
????????while?(ans.size()?!=?max)?{
????????????ans.add(nums[idx]);
????????????idx?=?g[idx];
????????}
????????return?ans;
????}
}

C++ 代碼：

class?Solution?{
public:
????vector<int>?largestDivisibleSubset(vector<int>&?nums)?{
????????sort(nums.begin(),?nums.end());
????????int?n?=?nums.size();
????????vector<int>?f(n,?0),?g(n,?0);
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????int?len?=?1,?prev?=?i;
????????????for?(int?j?=?0;?j?<?i;?j++)?{
????????????????if?(nums[i]?%?nums[j]?==?0)?{
????????????????????if?(f[j]?+?1?>?len)?{
????????????????????????len?=?f[j]?+?1;
????????????????????????prev?=?j;
????????????????????}
????????????????}
????????????}
????????????f[i]?=?len;?g[i]?=?prev;
????????}
????????int?max?=?-1,?idx?=?-1;
????????for?(int?i?=?0;?i?<?n;?i++)?{
????????????if?(f[i]?>?max)?{
????????????????max?=?f[i];
????????????????idx?=?i;
????????????}
????????}
????????vector<int>?ans;
????????while?(ans.size()?!=?max)?{
????????????ans.push_back(nums[idx]);
????????????idx?=?g[idx];
????????}
????????return?ans;
????}
};

Python 代碼：

class?Solution:
????def?largestDivisibleSubset(self,?nums:?List[int])?->?List[int]:
????????nums.sort()
????????n?=?len(nums)
????????f,?g?=?[0]?*?n,?[0]?*?n
????????for?i?in?range(n):
????????????lenv,?prev?=?1,?i
????????????for?j?in?range(i):
????????????????if?nums[i]?%?nums[j]?==?0:
????????????????????if?f[j]?+?1?>?lenv:
????????????????????????lenv,?prev?=?f[j]?+?1,?j
????????????f[i],?g[i]?=?lenv,?prev
????????maxv,?idx?=?-1,?-1
????????for?i?in?range(n):
????????????if?f[i]?>?maxv:
????????????????maxv,?idx?=?f[i],?i
????????ans?=?[]
????????while?len(ans)?!=?maxv:
????????????ans.append(nums[idx])
????????????idx?=?g[idx]
????????return?ans

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

證明

「之所以上述解法能夠成立，問題能夠轉(zhuǎn)化為「最長上升子序列（LIS）」問題進(jìn)行求解，本質(zhì)是利用了「全序關(guān)系」中的「可傳遞性」?！?/strong>