\u4e5f\u7b97\u662f\u4e00\u9053\u6bd4\u8f83\u7ecf\u5178\u7684DP\u9898\u4e86\uff0c\u9700\u8981\u627e\u5230\u4e00\u4e2a\u6700\u5927\u7684\u5b50\u96c6\uff0c\u4f7f\u5f97\u5176\u4e2d\u5143\u7d20\u4e24\u4e24\u7684\u4f59\u6570\u4e3a0\u3002<\/p>\n\n\n\n
\u6211\u4eec\u5047\u8bbe\u6709\u4e00\u4e2a\u96c6\u5408\u4e3a{a1, a2, a3, …, an}, {a1 < a2 < … < an)<\/p>\n\n\n\n
\u5982\u679c a2 % a1 = 0, a3 % a2 == 0, \u90a3\u4e48a3 % a1 \u4e00\u5b9a\u4e5f\u7b49\u4e8e0\u3002\u4e5f\u5c31\u662f\u8bf4a2\u662fa1\u7684\u500d\u6570\uff0ca3\u662fa2\u7684\u500d\u6570\uff0c\u90a3\u4e48a3\u4e00\u5b9a\u4e5f\u662fa1\u7684\u500d\u6570\u3002\u6240\u4ee5\u6211\u4eec\u5e76\u4e0d\u9700\u8981\u6d4b\u8bd5\u4efb\u610f\u4e24\u4e2a\u5143\u7d20\u4e4b\u95f4\u7684\u4f59\u6570\u4e3a0\uff0c\u6211\u4eec\u53ea\u9700\u8981\u68c0\u6d4ba[i]\u662f\u5426\u4e3aa[i-1]\u7684\u500d\u6570\u5373\u53ef\uff0c\u5982\u679c\u6210\u7acb\uff0c\u5219\u53ef\u4ee5\u786e\u4fdda[i]\u4e5f\u662fa[i-2], a[i-3], … a[1]\u7684\u500d\u6570\u3002\u8fd9\u6837\u5c31\u53ef\u4ee5\u5927\u5927\u964d\u4f4e\u95ee\u9898\u7684\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n
\u63a5\u4e0b\u6765\u5c31\u9700\u8981dp\u5c31\u53d1\u6325\u5a01\u529b\u4e86\u3002\u6211\u4eec\u5c06\u539f\u6570\u7ec4\u6392\u5e8f\uff0c\u7528dp[i]\u6765\u8868\u793a\u4ee5a[i]\u7ed3\u5c3e\uff08\u96c6\u5408\u4e2d\u7684\u6700\u5927\u503c\uff09\uff0c\u80fd\u591f\u6784\u5efa\u7684\u5b50\u96c6\u7684\u6700\u5927\u957f\u5ea6\u3002<\/p>\n\n\n\n
\u8f6c\u79fb\u65b9\u7a0b\uff1adp[j] = max(dp[j], dp[i] + 1) if nums[j] % nums[i] = 0.<\/p>\n\n\n\n
\u8fd9\u8868\u793a\uff0c\u5982\u679cnums[j] \u662f nums[i]\u7684\u500d\u6570\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u628anums[j]\u52a0\u5165\u4ee5nums[i]\u7ed3\u5c3e\u7684\u6700\u5927\u5b50\u96c6\u4e2d\uff0c\u6784\u5efa\u4e00\u4e2a\u65b0\u7684\u6700\u5927\u5b50\u96c6\uff0c\u957f\u5ea6+1\u3002\u5f53\u7136\u5bf9\u4e8ej\uff0c\u53ef\u80fd\u6709\u597d\u591a\u4e2a\u6ee1\u8db3\u6761\u4ef6\u7684i\uff0c\u6211\u4eec\u9700\u8981\u627e\u4e00\u4e2a\u6700\u5927\u7684\u3002<\/p>\n\n\n\n
\u4e3e\u4e2a\u4f8b\u5b50\uff1a
nums = {2, 3, 4, 12}
\u4ee53\u7ed3\u5c3e\u7684\u6700\u5927\u5b50\u96c6{3}\uff0c\u957f\u5ea6\u4e3a1\u3002\u7531\u4e8e12%3==0\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u628a12\u8ffd\u52a0\u5230{3} \u4e2d\uff0c\u6784\u6210{3,12}\u3002
\u4ee54\u7ed3\u5c3e\u7684\u6700\u5927\u5b50\u96c6\u662f{2,4}\uff0c\u957f\u5ea6\u4e3a2\u3002\u7531\u4e8e12%4==0\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u4ee5\u628a12\u8ffd\u52a0\u5230{2,4} \u4e2d\uff0c\u6784\u6210{2,4,12} \u3002\u5f97\u5230\u6700\u4f18\u89e3\u3002<\/p>\n\n\n\n
\u8fd9\u6837\u6211\u4eec\u53ea\u9700\u8981\u53cc\u91cd\u5faa\u73af\uff0c\u679a\u4e3ei\uff0c\u518d\u679a\u4e3ej (0 <= i < j)\u3002\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n^2)\u3002\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n)\u3002<\/p>\n\n\n\n
\u6700\u540e\u9700\u8981\u8f93\u51fa\u4e00\u4e2a\u6700\u5927\u5b50\u96c6\uff0c\u5982\u679c\u4e0d\u8bb0\u5f55\u9012\u63a8\u8fc7\u7a0b\uff0c\u5219\u9700\u8981\u7a0d\u5fae\u5224\u65ad\u4e00\u4e0b\u3002<\/p>\n\n\n\n
\nclass Solution {\npublic:\n vector largestDivisibleSubset(vector& nums) {\n const int n = nums.size();\n sort(begin(nums), end(nums));\n \/\/ dp[i] = max size of subset ends with nums[i]\n vector dp(n);\n for (int i = 0; i < n; ++i)\n for (int j = i + 1; j < n; ++j)\n if (nums[j] % nums[i] == 0)\n dp[j] = max(dp[j], dp[i] + 1);\n int s = *max_element(begin(dp), end(dp));\n vector ans;\n for (int i = n - 1; i >= 0; --i) {\n if (dp[i] == s && (ans.empty() || ans.back() % nums[i] == 0)) {\n ans.push_back(nums[i]);\n --s;\n }\n }\n return ans;\n }\n};\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e5f\u7b97\u662f\u4e00\u9053\u6bd4\u8f83\u7ecf\u5178\u7684DP\u9898\u4e86\uff0c\u9700\u8981\u627e\u5230\u4e00\u4e2a\u6700\u5927\u7684\u5b50\u96c6\uff0c\u4f7f\u5f97\u5176\u4e2d\u5143\u7d20\u4e24\u4e24\u7684\u4f59\u6570\u4e3a0\u3002 \u6211\u4eec\u5047\u8bbe\u6709\u4e00\u4e2a\u96c6\u5408\u4e3a{a1, a2, a3, …, an}, {a1 < a2 < … < an) \u5982\u679c a2 % a1 = 0, a3 % a2 == 0, \u90a3\u4e48a3…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,23,493,240],"class_list":["post-10266","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-sort","tag-subset","tag-unique","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10266"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10266\/revisions"}],"predecessor-version":[{"id":10271,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10266\/revisions\/10271"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}