Python小白的LeetcodeDailyChallenge刷题计划-20240209（除夕）

368. Largest Divisible Subset

难度：Medium

动态规划 + 方案还原

Yesterday's Daily Challenge can be reduced to the problem of shortest path in an unweighted graph while today's daily challenge can be reduced to the problem of longest path in an unweighted graph. Happy Chinese New Year!

class Solution: def largestDivisibleSubset(self, nums: list[int]) -> list[int]: n = len(nums) nums.sort() f, pre = [1]*n, [-1]*n t = 0 for i in range(n): for j in range(i): if nums[i] % nums[j] == 0: if f[j]+1 > f[i]: f[i] = f[j]+1 pre[i] = j if f[i] > f[t]: t = i ans = [] while t != -1: ans.append(nums[t]) t = pre[t] return ans def test(): samples = [[1,2,3], [1,2,4,8]] sol = Solution() for nums in samples: print(sol.largestDivisibleSubset(nums)) if __name__ == '__main__': test()