面试官追问‘数字n的拆分方案数’？从暴力递归到一维DP的完整优化路径

面试官追问‘数字n的拆分方案数’从暴力递归到一维DP的完整优化路径当面试官在白板上写下数字n的拆分方案数时大多数候选人的第一反应是尝试列举几个简单案例。比如n3时有3种划分321111n4时有5种划分。但真正的挑战在于如何系统化地解决这个问题并能在面试压力下清晰地展示思维演进过程。本文将还原一个完整的技术面试场景展示从最朴素的暴力解法到空间优化DP的完整思考链条。1. 从暴力递归开始理解问题本质面对划分问题时首先要明确有序划分和无序划分的区别。我们讨论的是无序划分即12和21视为同一种方案。这直接影响后续算法的设计。1.1 递归定义与实现定义dfs(n, m)表示将整数n划分为最大加数不超过m的方案数。递归的边界条件当n0时表示划分完成算作1种有效方案当m0时且n0时表示无法划分返回0当mn时等价于dfs(n,n)核心递归关系def count_partitions(n, m): if n 0: return 1 if m 0: return 0 if m n: return count_partitions(n, n) return count_partitions(n, m-1) count_partitions(n-m, m)1.2 复杂度分析与问题暴露对于n6的递归树分析(6,6) / \ (6,5) (0,6) / \ | (6,4) (1,5) 1 / \ | (6,3) (2,4) (1,4)显然存在大量重复计算如(1,4)会被多次计算。时间复杂度达到O(2^n)完全无法处理n30的情况。面试技巧在写出递归解法后主动指出其缺陷并给出复杂度分析展示问题意识2. 记忆化搜索消除重复子问题2.1 引入缓存机制添加一个二维数组memo[n][m]存储已计算结果memo [[-1]*(n1) for _ in range(n1)] def count_partitions_memo(n, m): if n 0: return 1 if m 0: return 0 if memo[n][m] ! -1: return memo[n][m] if m n: memo[n][m] count_partitions_memo(n, n) return memo[n][m] memo[n][m] count_partitions_memo(n, m-1) count_partitions_memo(n-m, m) return memo[n][m]2.2 复杂度优化效果通过记忆化时间复杂度降为O(n^2)共有n^2个子问题空间复杂度O(n^2)需要存储整个二维数组此时已经可以处理n1000量级的问题但仍有优化空间。3. 标准二维DP自底向上填表3.1 状态转移方程将递归转为迭代定义dp[i][j]表示整数i划分为最大加数不超过j的方案数dp[i][j] dp[i][j-1] dp[i-j][j] (当i j) dp[i][j] dp[i][i] (当i j)边界条件dp[0][j] 1空划分dp[i][0] 0i0时3.2 实现代码示例def count_partitions_dp(n): dp [[0]*(n1) for _ in range(n1)] for j in range(n1): dp[0][j] 1 for i in range(1, n1): for j in range(1, n1): if j i: dp[i][j] dp[i][i] else: dp[i][j] dp[i][j-1] dp[i-j][j] return dp[n][n]3.3 面试常见追问面试官可能会问为什么初始化dp[0][j]1如何处理ji的情况能否解释状态转移方程的实际意义准备答案空划分是有效的划分方案当最大加数超过目标数时等价于最大加数等于目标数将划分分为不包含j和至少包含一个j两种情况4. 空间优化一维DP的魔法4.1 观察空间依赖仔细分析二维DP的更新过程发现当前行只依赖当前行和上一行的某些位置可以通过调整计算顺序仅使用一维数组4.2 优化后的递推关系定义dp[i]表示整数i的划分数则有dp[i] dp[i-j] (j从1到n)需要按特定顺序更新def count_partitions_optimized(n): dp [0]*(n1) dp[0] 1 for j in range(1, n1): # 注意j的遍历顺序 for i in range(j, n1): dp[i] dp[i-j] return dp[n]4.3 复杂度对比方法时间复杂度空间复杂度暴力递归O(2^n)O(n)记忆化搜索O(n^2)O(n^2)二维DPO(n^2)O(n^2)一维DPO(n^2)O(n)5. 面试实战应对各种变体问题5.1 变体1限制划分数字个数求恰好划分为k个数字的方案数解法def count_k_partitions(n, k): dp [[0]*(k1) for _ in range(n1)] dp[0][0] 1 for i in range(1, n1): for j in range(1, k1): if i j: dp[i][j] dp[i-1][j-1] dp[i-j][j] return dp[n][k]5.2 变体2限制使用奇数划分只能用奇数进行划分的解决方案def count_odd_partitions(n): dp [0]*(n1) dp[0] 1 for j in range(1, n1, 2): # 只遍历奇数 for i in range(j, n1): dp[i] dp[i-j] return dp[n]5.3 变体3唯一划分不重复使用数字每个数字最多使用一次的解决方案def count_unique_partitions(n): dp [0]*(n1) dp[0] 1 for j in range(1, n1): for i in range(n, j-1, -1): # 反向遍历避免重复使用 dp[i] dp[i-j] return dp[n]6. 系统设计视角的延伸思考在实际工程应用中整数划分问题可以建模多种场景资源分配方案计算支付系统的找零组合任务拆分的可能性评估当n很大时如n10^5可能需要使用模数避免整数溢出考虑并行计算优化应用数论中的五边形数定理O(n√n)算法# 五边形数定理实现示例高级解法 def pentagonal(n): return n*(3*n-1)//2 def count_partitions_advanced(n, modNone): dp [0]*(n1) dp[0] 1 for i in range(1, n1): j, k 1, 1 while True: g pentagonal(j) if g i: break dp[i] dp[i-g] * (-1)**(k1) g pentagonal(-j) if g i: break dp[i] dp[i-g] * (-1)**(k1) j 1 k 1 if mod: dp[i] % mod return dp[n]在面试的最后阶段展示对不同场景的思考深度往往能获得加分。比如讨论当n极大时如何设计分布式解决方案或者如何用生成函数方法解决这个问题。