1. 问题背景与需求拆解小明减肥这道算法题源自华为OD机考双机位A卷题目描述大致为小明需要在N天内通过运动减肥每天有若干种运动方式可选每种运动消耗不同的卡路里。要求找出所有满足总消耗卡路里等于目标值的运动组合。这本质上是一个典型的组合求和问题需要找出所有可能的解集。这类问题在实际开发中非常常见比如电商平台的优惠券组合计算、金融领域的投资组合优化、游戏装备搭配等场景。题目考察的核心能力是对回溯算法和动态规划两种经典解法的掌握程度以及在实际编码中的实现细节把控。2. 回溯法解决方案详解2.1 回溯算法核心思想回溯法通过递归尝试所有可能的候选解当发现当前路径不可能得到正确解时立即回退到上一步选择其他路径。对于组合问题其时间复杂度为O(2^n)属于暴力搜索的优化版本。具体到本题我们可以将每天的运动选项视为决策树的一个层级递归尝试每种运动选择当累计卡路里等于目标值时记录解当累计值超过目标时剪枝返回2.2 代码实现与关键点def backtrack(days, target): res [] def dfs(day_idx, path, current_cal): if current_cal target: res.append(path.copy()) return if current_cal target or day_idx len(days): return # 尝试当天所有运动选择 for exercise in days[day_idx]: path.append(exercise) dfs(day_idx 1, path, current_cal exercise) path.pop() # 回溯 dfs(0, [], 0) return res关键注意事项必须使用path.copy()保存结果否则会得到空列表剪枝条件(current_cal target)能显著提升效率递归深度与天数成正比当N较大时需注意栈溢出风险2.3 复杂度分析与优化最坏情况下需要遍历所有可能的组合时间复杂度为O(M^N)M为每日平均运动选项数。实际可以通过以下优化预处理时按卡路里值排序便于提前剪枝使用记忆化存储中间结果但效果有限对于有重复运动的情况需要进行去重处理3. 动态规划解决方案3.1 DP解题思路转换动态规划将问题转化为dp[i][j]表示前i天消耗j卡路里的所有组合。状态转移方程为dp[i][j] ∪ (dp[i-1][j - k] [k]) ∀k ∈ days[i]这实际上是一个带路径记录的多重背包问题。3.2 递推实现版本def dp_solution(days, target): dp [ [] for _ in range(target 1) ] dp[0] [ [] ] # 初始状态 for day in days: new_dp [ [] for _ in range(target 1) ] for cal in range(target 1): if not dp[cal]: continue for exercise in day: new_cal cal exercise if new_cal target: continue for seq in dp[cal]: new_dp[new_cal].append(seq [exercise]) dp new_dp return dp[target]3.3 空间优化技巧原始DP需要O(N*Target)空间可以通过以下方式优化使用滚动数组减少空间到O(Target)对运动选项进行预处理合并相同卡路里值当target很大时可以先进行可行性判断注意DP解法在target值较大时会出现内存问题而回溯法则不受此限制4. 两种方法的对比选择4.1 适用场景分析维度回溯法动态规划时间复杂度O(M^N)O(NMTarget)空间复杂度O(N)递归栈O(N*Target)最佳场景需要所有解、选项少求最优解、target适中优势实现简单、无需额外空间无重复计算劣势存在重复计算大target时内存爆炸4.2 华为机考实战建议明确题目要求如果要求所有解优先考虑回溯法注意输入规模当N20时回溯可能超时边界条件处理空输入、target为0等特殊情况输出顺序要求有些题目要求按特定顺序输出5. 常见陷阱与调试技巧5.1 典型错误案例未处理重复解# 错误示例当days中有重复运动时会产生重复解 def dfs(day_idx, path): ... for i in range(len(days[day_idx])): dfs(day_idx1, path [days[day_idx][i]])错误的剪枝条件# 错误示例缺少day_idx边界检查会导致数组越界 if current_cal target: return5.2 调试方法论打印决策树路径在递归入口和出口打印关键变量小规模测试先用2天3种运动的简单case验证内存监控对于DP解法打印dp数组大小性能分析使用timeit模块比较不同输入的耗时5.3 测试用例设计有效测试应当包含常规case3天每天2-3种运动边界casetarget为0或极大值特殊case所有运动卡路里相同性能caseN20的大规模数据示例测试集test_cases [ ([[1,2],[3,4]], 5, [[1,4],[2,3]]), ([[1,1,2],[2,2,3]], 4, [[1,3],[2,2]]), ([[5]], 5, [[5]]), ([[1,2],[3,4]], 10, []), ]6. 算法扩展与变种6.1 限制条件下的变种运动次数限制每种运动最多选k次连续性约束不能连续选择相同运动成本最小化在满足卡路里条件下使运动成本最小6.2 其他解法探讨记忆化回溯存储中间结果减少重复计算位运算枚举当N较小时可以用bitmask表示选择双向搜索将N天分为两半分别搜索再合并6.3 实际工程应用这类算法在以下场景有实用价值优惠券组合计算电商平台课程组合推荐在线教育药物配方优化医疗健康资源调度组合云计算我在实际项目中遇到过一个类似需求需要计算用户在不同促销活动下的最优优惠组合。最终采用回溯剪枝的混合策略当选项少于15种时用回溯法求精确解否则用贪心算法求近似解取得了不错的效果。
