算法题深度解析：最大回文数乘积高效解法，Python剪枝优化思路

算法题深度解析：最大回文数乘积高效解法，Python剪枝优化思路

刚刷到一个有趣的帖子，讲的是职场私活背后的“人情债”，虽然和算法无关，但那股子“被坑了还得自我安慰”的劲头，倒和咱们调试代码时的心态有几分相似——明明可以更优雅，却总有人选择绕远路。

今天聊的这道算法题，就很有这种“看似简单，实则讲究”的味道。

从一道算法题说起：最大回文数乘积

题目是找出两个三位数相乘能得到的最大回文数。很多人第一反应就是暴力枚举，把 100 到 999 之间的所有组合算一遍。代码虽然能跑，但那是机器在蛮干，不是算法在思考。

要写好这道题，得先抓住核心：

1. 如何判断回文：把数字转成字符串，反转后比较即可。Python 处理这个非常自然。
2. 如何减少计算量：既然要找最大值，循环就从大到小遍历。一旦当前乘积已经无法超越已有答案，立即剪枝。

先看一个高效且清晰的版本：

def is_palindrome(n: int) -> bool:
    s = str(n)
    return s == s[::-1]

def largest_palindrome_product() -> int:
    best = 0

    for a in range(999, 99, -1):
        if a * 999 < best:
            break

        for b in range(999, a - 1, -1):
            product = a * b

            if product <= best:
                break

            if is_palindrome(product):
                best = product
                break

    return best

print(largest_palindrome_product())

这段代码里有几个关键优化点值得琢磨：

• *`if a 999 < best**：当外层的a已经小到连乘以最大可能的b（即 999）都超不过当前最佳答案best时，后面更小的a` 就完全不必考虑了。
• if product <= best：内层循环的 b 也是从大到小递减的。一旦乘积 product 小于等于当前的最佳值，后续的 b 只会更小，乘积也不可能更大，可以直接跳出内层循环。

最终答案是 906609，对应的是 *`913 993`**。

当然，也有更偏数学的解法，比如先直接构造回文数，再尝试分解为两个三位数的乘积。那种思路理论上更漂亮，但在面试或笔试中，能先写清楚一个剪枝到位、复杂度明显收窄的版本，其实更显功底。

一个不太推荐的反面示例

很多人会顺手写出下面这种粗暴的版本：

best = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        val = a * b
        if str(val) == str(val)[::-1]:
            best = max(best, val)

这段代码的问题不是错，而是笨。它把所有对称的乘法（比如 913 * 993 和 993 * 913）都算了两遍，而且没有任何提前停止的意识。数据规模一大，这个写法就容易露怯。

所以，这道题考察的真正价值在于：你不仅要会判断回文，更要让人看出你知道从哪下刀能省力。

如果你对更多算法题解或职场摸鱼技巧感兴趣，欢迎随时来 开发者社区 的 云栈社区 逛逛。