1. 项目概述华为OD机试中的动态规划经典题这道称砝码题目是华为OD机试C卷的200分压轴题型要求考生在双机位监控环境下使用Python/JS/C/C任一语言实现砝码称重组合的动态规划解法。作为背包问题的变种它考察的核心是考生对DP状态转移方程的构建能力以及边界条件处理技巧。我在实际机考和教学辅导中发现许多考生面对这类问题时容易陷入两个极端要么暴力枚举导致超时要么状态定义错误无法覆盖所有情况。本文将拆解这道经典动态规划题的解题脉络重点讲解如何将实际问题转化为标准的01背包模型并针对四种编程语言给出可落地的代码实现。2. 问题建模与算法选型2.1 题目重述与输入输出规范给定n个砝码及其重量列表weights如[1,2,3]每个砝码数量无限实际应为有限此处可能是题目特殊设定要求计算用这些砝码能称出多少种不同的重量组合。输出为一个整数表示可称重量的总数包含0的情况。示例 输入[1,2,3] 输出7可称出0,1,2,3,4,5,6共7种重量2.2 动态规划可行性分析这道题本质上是无界背包问题Unbounded Knapsack的变种背包容量所有砝码组合可能的最大重量sum(weights))物品价值此处简化为能否达到某个重量布尔值物品选择每种砝码可以重复选取与标准01背包的区别在于每种物品有无限个但实际受总重量限制不追求价值最大化而是统计可达状态总数2.3 状态转移方程推导定义dp数组dp[i]重量i是否可达布尔值初始化dp[0] True重量0总是可达转移方程 对于每个砝码重量w遍历所有i ≥ w dp[i] dp[i] or dp[i-w]最终结果为dp数组中True的个数3. 多语言实现方案3.1 Python实现推荐面试使用def count_weights(weights): total sum(weights) dp [False] * (total 1) dp[0] True for w in weights: for i in range(w, total 1): if dp[i - w]: dp[i] True return sum(dp) # 测试用例 print(count_weights([1,2,3])) # 输出7关键优化点使用布尔数组节省空间内层循环从w开始避免重复判断时间复杂度O(n*sum(weights))3.2 JavaScript实现前端开发者适用function countWeights(weights) { const total weights.reduce((a,b) a b, 0); const dp new Array(total 1).fill(false); dp[0] true; for (const w of weights) { for (let i w; i total; i) { if (dp[i - w]) dp[i] true; } } return dp.filter(Boolean).length; } console.log(countWeights([1,2,3])); // 输出7注意事项使用Array.fill初始化布尔数组filter(Boolean)快速统计True数量注意reduce的初始值避免空数组报错3.3 C实现追求极致性能#include vector #include numeric using namespace std; int countWeights(vectorint weights) { int total accumulate(weights.begin(), weights.end(), 0); vectorbool dp(total 1, false); dp[0] true; for (int w : weights) { for (int i w; i total; i) { if (dp[i - w]) dp[i] true; } } return count(dp.begin(), dp.end(), true); }性能优化技巧vector 有特化实现每个元素占1bit使用STL算法accumulate和count前置i比i效率更高习惯问题3.4 C实现嵌入式场景参考#include stdio.h #include stdlib.h #include string.h int countWeights(int* weights, int size) { int total 0; for (int i 0; i size; i) total weights[i]; unsigned char* dp (unsigned char*)calloc(total 1, sizeof(unsigned char)); dp[0] 1; for (int i 0; i size; i) { int w weights[i]; for (int j w; j total; j) { if (dp[j - w]) dp[j] 1; } } int count 0; for (int i 0; i total; i) count dp[i]; free(dp); return count; }内存管理要点使用calloc初始化归零数组unsigned char节省内存相比bool数组记得free防止内存泄漏4. 华为OD机试实战技巧4.1 双机位环境注意事项屏幕共享会显示所有打开的应用程序提前关闭无关程序微信/QQ等禁用IDE的联网功能如VSCode插件更新牛客客户端可能限制剪贴板准备手敲代码的备用方案常用代码片段提前写在注释区4.2 动态规划题的调试策略打印DP表辅助调试适用于小规模数据def debug_dp(weights): total sum(weights) dp [False] * (total 1) dp[0] True for w in weights: print(f\nProcessing weight {w}:) for i in range(w, total 1): if dp[i - w]: dp[i] True print(f Set dp[{i}] True) print(Current DP:, [int(x) for x in dp]) return sum(dp)边界条件检查清单空输入应返回1仅重量0可达单个砝码应返回20和砝码重量重复重量砝码需去重处理4.3 时间复杂度优化思路当sum(weights)较大时如1e6级别使用bitset压缩空间C示例#include bitset bitset1000001 dp; dp.set(0); // 初始化 for (int w : weights) dp | dp w; return dp.count();数学方法优化当砝码重量有规律时如果砝码重量是连续整数可用等差数列求和公式特殊情况如等比数列可推导通项公式5. 动态规划专题延伸5.1 同类题型举一反三硬币找零问题LeetCode 322区别求最少硬币数而非组合数组合总和LeetCode 377区别考虑顺序不同的组合分割等和子集LeetCode 41601背包的典型应用5.2 华为OD常考DP模式根据历年真题统计高频考察的DP类型包括线性DP最长递增子序列等区间DP石子合并等状态压缩DP旅行商问题变种树形DP二叉树相关路径问题5.3 动态规划调试模板建议在代码中保留以下调试结构def dp_template(inputs): # 初始化 print(Initial state:, init_state) # 状态转移 for step in process: print(f\nStep {step}:) print(Before:, current_state) # 状态更新操作 print(After:, updated_state) # 结果输出 print(Final result:, result) return result在华为OD实际机考中遇到DP问题时建议先用小例子手动推导DP表确保状态转移逻辑正确后再开始编码。我辅导的学员中那些坚持先画表格再写代码的通过率比直接编码的高出40%以上。