从离职同事返岗尴尬场面，聊聊算法面试中的动态规划思路

去年走得最潇洒的那位同事，离职四个月后，突然又推门回到了公司。他一脸轻松，像往常一样冲大家挥手打招呼：“嘿，我又回来上班了。”

这场面，说实话，隔着屏幕都能感觉到空气中弥漫的尴尬。更绝的是，同事们一个个面无表情，没人接他的话茬，气氛瞬间就凝固了。

回想他当初离开时的样子，可不是这副光景。那时他满口都是对公司的不满，觉得这里不好那里不行，话里话外都透着一股“外面机会遍地，我早就该走”的自信。结果出去转了一圈才发现，理想很丰满，现实却往往连个合适的工位都难找。

这情况在职场上其实并不稀奇。很多人意气风发地离职，真到了新环境才发现，老板是换了，但“画饼”的方式可能如出一辙；工资看似涨了一点，但背后要填的“坑”可能更深。最尴尬的或许不是回来这件事本身，而是回来之后，还得努力装作一切如常。你说这是脸皮厚吗？或许也是被现实生活磨平了棱角。成年人的世界，有时候体面真的没有端稳一个饭碗来得重要。

聊完这个有点扎心的职场插曲，我们换个频道，来聊聊更硬核的东西——算法面试。这不，刚好有一道与“选择”和“最长链”相关的题目，和上面那个关于“出去又回来”的选择故事，在逻辑上倒有几分异曲同工之妙。

算法题：最大整除子集

这道题叫做 最大整除子集。题面不长，但如果你一上来就想用回溯法硬搜，十有八九会超时。因为它问的不是“有没有一种选法”，而是“最长能选到多长”，这种求极值的“味道”，其实已经强烈暗示了动态规划的方向。

解题的第一步很关键：先把数组排个序。排序之后，如果 nums[i] % nums[j] == 0，那就说明 nums[i] 有可能接在 nums[j] 的后面，从而形成一个更长的“整除链”。一旦顺序固定，问题就从抽象的“子集”问题，转变成了我们更熟悉的“最长递增子序列”类问题的变种。

举个例子：

nums = [1, 2, 3, 8, 4, 12]
nums.sort()
print(nums)   # 输出：[1, 2, 3, 4, 8, 12]

排序之后再观察，整除关系就清晰多了：8 可以接在 4 后面，4 可以接在 2 后面，2 可以接在 1 后面，一条完整的链路就浮现出来了。

通常，我们会定义两个数组来辅助解决：

• dp[i]：表示以 nums[i] 这个数字结尾的，能够形成的最大整除子集的长度。
• prev[i]：记录当前下标 i 是从之前哪个下标 j 转移过来的，方便我们最后回溯构造出这个最长的子集。

核心的状态转移逻辑其实非常简洁：

for i in range(n):
    for j in range(i):
        if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1
            prev[i] = j

完整的参考代码如下，这种写法在面试中足够清晰，也容易解释：

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        nums.sort()
        n = len(nums)
        dp = [1] * n          # 每个元素至少可以单独成为子集
        prev = [-1] * n       # -1 表示是子集的起点

        max_len = 1
        max_idx = 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        prev[i] = j

            if dp[i] > max_len:
                max_len = dp[i]
                max_idx = i

        # 回溯构造结果
        ans = []
        while max_idx != -1:
            ans.append(nums[max_idx])
            max_idx = prev[max_idx]

        return ans[::-1]  # 因为是从后往前添加的，所以需要反转

我们用 nums = [1, 2, 4, 8] 这个例子跑一下，算法运行后：

dp = [1, 2, 3, 4]
prev = [-1, 0, 1, 2]

最后从 max_idx = 3 开始回溯，得到的结果就是 [1, 2, 4, 8]。

这道题有一个容易让人想偏的地方：它要求的是子集，而不是子序列，所以很多人会觉得顺序不重要，想直接在原数组上操作。其实，恰恰因为顺序不重要，我们才更应该先排序。排序之后，前面的数更小，后面的数更大，整除关系的判断就变成了单向的，状态转移也因此变得更加稳定和清晰。

这道题的时间复杂度是 O(n^2)，空间复杂度是 O(n)。上面这套写法在面试中是比较稳妥的，它不追求奇技淫巧，但足够实用。真正的难点往往不在于写出代码，而在于最初如何将“寻找一个最大子集”的问题，转化建模为“寻找以某个数结尾的最长整除链”的动态规划问题。这个思维上的弯一旦转过来，后面的编码就是水到渠成。

无论是面对职场去留的抉择，还是解决一道算法题，清晰的思路和对问题本质的洞察都至关重要。生活中这些看似不相关的场景，其实都在锻炼我们分析问题、规划路径的能力。如果你对这类融合了现实观察与技术思考的话题感兴趣，欢迎来开发者广场逛逛，这里常有类似的分享与讨论。