从PTA『凑零钱』到LeetCode：掌握‘带选择记录’的动态规划通用解法

从硬币组合到路径回溯动态规划中状态转移的完整追踪技术在算法竞赛和编程面试中动态规划(DP)问题占据了重要地位。大多数教程都聚焦于如何计算最优解的值却很少深入探讨如何记录和回溯得到这个解的具体构成路径。这种知其值而不知其所以然的情况在面对需要输出具体方案而非单纯数值结果的问题时往往让学习者感到束手无策。1. 动态规划的本质与路径记录需求动态规划之所以高效在于它通过存储子问题的解避免了重复计算。传统DP问题如经典的0-1背包通常只关心最终的最大价值或最优解数值而无需知道这个数值是如何组合而来的。但在实际应用中我们常常需要知道这个最优解的具体构成。以硬币找零问题为例假设我们有面额为[1,2,5]的硬币无限供应要凑出金额11。标准的DP解法会告诉我们最少需要3枚硬币(551)但不会告诉我们具体是哪几个硬币。而在实际场景中ATM机需要输出具体纸币物流装箱需要知道具体物品组合这时就需要记录状态转移路径。路径记录DP与传统DP的核心区别在于传统DPdp[i][j]仅存储子问题的最优值路径记录DP额外维护一个choice[i][j]数组记录达到这个状态所做的选择# 传统硬币找零DP def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1 # 带路径记录的硬币找零DP def coinChangeWithPath(coins, amount): dp [float(inf)] * (amount 1) path [-1] * (amount 1) # 记录转移来源 dp[0] 0 for coin in coins: for i in range(coin, amount 1): if dp[i - coin] 1 dp[i]: dp[i] dp[i - coin] 1 path[i] i - coin # 记录状态转移来源 # 回溯路径 if dp[amount] float(inf): return -1, [] res [] current amount while current 0: res.append(current - path[current]) current path[current] return dp[amount], res2. 状态标记与路径回溯的通用框架通过分析各类需要输出具体解的问题我们可以提炼出一个四步通用框架2.1 状态定义与传统DP相同需要明确定义状态表示什么。以0-1背包为例dp[i][j]: 考虑前i件物品背包容量为j时的最大价值choice[i][j]: 记录在状态(i,j)下是否选择了第i件物品2.2 状态转移与选择标记在进行状态转移时不仅要更新最优值还要记录选择for i in range(1, n1): for j in range(1, capacity1): if j weight[i-1]: if dp[i-1][j] dp[i-1][j-weight[i-1]] value[i-1]: dp[i][j] dp[i-1][j] choice[i][j] 0 # 不选当前物品 else: dp[i][j] dp[i-1][j-weight[i-1]] value[i-1] choice[i][j] 1 # 选择当前物品 else: dp[i][j] dp[i-1][j] choice[i][j] 02.3 回溯路径从最终状态倒推根据choice数组重建选择路径def trace_back(choice, weights): i, j len(choice)-1, len(choice[0])-1 selected [] while i 0 and j 0: if choice[i][j] 1: selected.append(i-1) # 记录物品索引 j - weights[i-1] i - 1 return selected[::-1] # 反转得到正序2.4 框架总结步骤操作数据结构说明状态定义定义dp和choice数组dp数组, choice数组明确状态含义状态转移更新dp并记录choice转移方程同时更新值和选择标记选择存储决策点choice数组记录转移来源或决策路径回溯从终点反向追踪递归或循环重建完整解决方案3. 经典问题变种的路径记录实现3.1 硬币找零问题PTA凑零钱问题要求输出字典序最小的硬币组合。这需要在标准硬币问题基础上增加排序和选择策略def coinChangeMinSequence(coins, amount): coins.sort(reverseTrue) # 从大到小排序 dp [float(inf)] * (amount 1) path [[] for _ in range(amount 1)] # 存储具体硬币组合 dp[0] 0 path[0] [] for coin in coins: for i in range(coin, amount 1): if dp[i - coin] 1 dp[i]: # 当硬币数相同时选择字典序更小的组合 if dp[i - coin] 1 dp[i]: new_path path[i - coin] [coin] if len(new_path) len(path[i]) and new_path path[i]: path[i] new_path else: dp[i] dp[i - coin] 1 path[i] path[i - coin] [coin] return path[amount] if dp[amount] ! float(inf) else None3.2 子集和问题给定一组正整数和一个目标和判断是否存在子集和等于目标并输出该子集def subsetSum(nums, target): n len(nums) dp [[False]*(target1) for _ in range(n1)] choice [[False]*(target1) for _ in range(n1)] dp[0][0] True for i in range(1, n1): for j in range(target1): if j nums[i-1]: if dp[i-1][j] or dp[i-1][j-nums[i-1]]: dp[i][j] True if dp[i-1][j-nums[i-1]]: choice[i][j] True # 选择当前数字 else: dp[i][j] dp[i-1][j] if not dp[n][target]: return None # 回溯路径 res [] j target for i in range(n, 0, -1): if choice[i][j]: res.append(nums[i-1]) j - nums[i-1] return res[::-1]4. 优化技巧与常见陷阱4.1 空间优化策略当处理大规模数据时二维DP可能消耗过多内存。我们可以优化空间但路径记录需要特殊处理def coinChangePathOptimized(coins, amount): dp [float(inf)] * (amount 1) path [[] for _ in range(amount 1)] # 存储路径 dp[0] 0 for coin in coins: for i in range(coin, amount 1): if dp[i - coin] 1 dp[i]: dp[i] dp[i - coin] 1 path[i] path[i - coin] [coin] # 更新路径 return path[amount] if dp[amount] ! float(inf) else None4.2 常见错误与调试技巧初始条件遗漏忘记初始化dp[0]或path[0]状态转移条件错误在更新路径时使用了不正确的比较条件回溯方向错误从前往后回溯而非从后往前字典序处理不当在需要最小字典序时未正确排序和比较调试建议打印出完整的dp表和choice表手动验证几个关键状态的选择和转移是否正确4.3 性能对比方法时间复杂度空间复杂度适用场景标准DPO(nW)O(nW)仅需最优值带路径DPO(nW)O(nW)需要具体解空间优化DPO(nW)O(W)大规模数据路径简单回溯法O(2^n)O(n)小规模数据需要所有解在实际编码中我发现路径记录DP虽然增加了空间复杂度但在面试和竞赛中能够完整展示解题思路和实现细节往往比单纯给出最优值更能体现算法能力。特别是在处理类似PTA凑零钱这类问题时正确的路径回溯可以成为区分普通和优秀解决方案的关键因素。