当前位置：首页 > news >正文

华为OD机试动态规划实战：从“小明减肥”题解看多约束状态设计

news 2026/8/12 20:35:18

1. 项目概述：从一道真题看华为OD机试的核心逻辑

最近在帮几个准备华为OD机试的朋友做辅导，发现大家普遍有个误区：觉得机试就是刷题，把题库里的答案背下来就行。这其实是个天大的误会。华为OD的机试，尤其是真题，其核心价值不在于让你记住某道题的解法，而在于通过一道具体的题目，考察你问题拆解、逻辑实现和工程化编码的综合能力。今天我就以一道非常经典的题目——“小明减肥”为例，带大家深入拆解一下，看看一道好的机试题背后，到底藏着哪些门道，以及如何用Python、Java、C++这三种主流语言，写出既正确又漂亮的代码。

“小明减肥”这个题目名听起来很生活化，但它本质上是一个动态规划（Dynamic Programming, DP）的变种问题，可能结合了背包问题的思想或者路径规划的逻辑。它绝不会简单地让你算个热量差，而是会设定一系列约束条件（比如每天运动时长限制、食物热量摄入、阶段性目标等），要求你找出在特定周期内达成减肥目标（如减重最大或耗时最短）的最优策略。这道题完美地模拟了软件开发中的一个常见场景：在有限的资源（时间、能量）和复杂的规则下，寻找最优解。这正是华为OD机试青睐的题型——它不考偏门算法，专考那些在真实业务开发中最常用、最体现程序员思维基本功的算法。

接下来，我会假设一个具体的、合理的题目描述，并围绕它展开。请注意，以下题目描述是我根据“小明减肥”这个标题和华为OD一贯的出题风格合理演绎的，旨在提供一个完整的分析靶子。在实际备考中，理解这种“从抽象标题到具体约束”的推演能力，比你死记硬背一个答案重要得多。

假设题目描述如下：

小明决定进行为期N天的减肥计划。他每天可以选择进行一项运动，消耗一定的卡路里（消耗值数组exercise[i]），同时也会摄入一定的食物热量（摄入值数组food[i]）。小明希望在这N天结束后，总消耗卡路里与总摄入卡路里的差值（即净消耗）最大。但是有两个限制：
连续运动天数不能超过K天，否则会受伤。
每天如果既运动又控制饮食（即净消耗为正），会产生疲劳度+1；如果休息（不运动），疲劳度清零。总疲劳度不能超过M。
请计算小明在N天结束后，能获得的最大净消耗卡路里值。
输入示例：N=5, K=2, M=1 exercise = [300, 200, 400, 100, 500] food = [200, 300, 100, 400, 200]
输出示例：900
解释（非标准输出部分，仅用于理解）：一种最优策略是：第1、2天运动，第3天休息，第4、5天运动。净消耗 = (300-200) + (200-300) + 0 + (100-400) + (500-200) = 100 - 100 + 0 - 300 + 300 = 0？等等，这里计算有误，我们重新规划。实际上，为了满足疲劳度M=1，需要更精细地安排休息日来清零疲劳度。这正体现了题目的复杂性。

看到这个假设的题目，是不是感觉立刻从“小明减肥”这个简单的名字，进入了一个需要仔细定义状态和状态转移方程的DP问题？我们接下来的所有分析，都将基于这个题目框架展开。无论你遇到的具体题目参数如何变化，这种将生活场景抽象为数学模型，并选用合适算法（本题是DP）解决的能力，才是机试的考察重点。

2. 核心思路与算法选型：为什么一定是动态规划？

拿到一个问题，尤其是机试场景下时间有限，快速准确地判断算法方向是成败的关键。对于“小明减肥”这类问题，我们如何第一时间锁定动态规划呢？

2.1 识别动态规划问题的经典特征

动态规划适用于求解具有以下特征的问题，而我们的假设题目几乎全中：

最优子结构：问题的最优解包含其子问题的最优解。在本题中，要计算N天结束后的最大净消耗，我们必须知道在第i天结束、处于某种状态（如连续运动了几天、当前疲劳度是多少）时的最大净消耗。第i天的状态最优解，必然由第i-1天的某些状态的最优解推导而来。
重叠子问题：在递归求解过程中，相同的子问题会被反复计算。例如，计算“第5天，连续运动1天，疲劳度为0”这个状态时，可能需要用到“第4天，连续运动0天（即休息），疲劳度为0”的状态。而这个状态在计算其他路径时也会被用到。如果使用暴力递归，会有大量重复计算，DP通过表格存储中间结果来避免这一点。
多阶段决策：问题可以按时间（天数）自然地分解为多个阶段，每天都需要做出一个决策（运动或休息），每个决策都会影响当前的状态（连续运动天数、疲劳度）并产生一个收益（当天的净消耗）。

当你发现题目中有“在...约束下，求最大/最小值”、“每一步的选择会影响后续状态”、“数据范围较大（N可能为1000或10000），暴力搜索不可行”这些信号时，就要高度怀疑这是DP问题。

2.2 状态定义与设计：解题的基石

DP最难也最关键的一步就是定义状态。状态定义得好，转移方程就清晰，代码也简洁；定义得不好，可能会把自己绕进去，或者产生冗余计算。

对于我们的假设题目，我们需要追踪哪些信息，才能完整描述“第i天结束那一刻”的局面，并且足以推导出后续决策？

经过分析，我们需要三个维度：

当前天数i：这是DP的阶段，通常作为DP数组的第一维，从0到N。
连续运动天数j：为了满足“连续运动不能超过K天”的限制，我们必须知道当前已经连续运动了多少天。j的范围是[0, K]。当j=K时，下一天必须休息。
当前疲劳度f：为了满足“总疲劳度不超过M”的限制，我们必须记录当前的疲劳度累计值。f的范围是[0, M]。

因此，我们可以定义一个三维DP数组：dp[i][j][f]：表示在第i天结束时，已经连续运动了j天，且当前疲劳度为f的情况下，能够获得的最大累计净消耗。

为什么状态要这么设计？

j记录连续运动天数，是为了强制执行“连续运动不超过K天”的约束。如果j == K，那么状态转移时就不能再转移到“运动”的状态。
f记录疲劳度，是为了强制执行“总疲劳度不超过M”的约束。同时，疲劳度的增减规则（运动且净消耗为正则+1，休息则清零）是状态转移逻辑的一部分。
净消耗的累计值，则是我们要求解的“最优值”，所以它作为DP数组存储的值。

状态初始化：dp[0][0][0] = 0，表示第0天（还没开始）时，连续运动0天，疲劳度0，净消耗为0。其他所有状态初始化为一个非常小的负数（如-inf），表示不可达状态。

2.3 状态转移方程推导：逻辑的核心

状态转移方程描述了如何从已知的前一天（i-1）的状态，通过今天的决策，推导出今天（i）的状态。决策有两种：今天运动，或者今天休息。

我们定义第i天的运动消耗为ex[i]，食物摄入为fd[i]，则当天净消耗net = ex[i] - fd[i]。

情况一：第i天选择运动前提条件：前一天的连续运动天数j_prev必须小于K（即j_prev < K），否则今天不能再运动。状态转移：

新的连续运动天数：j_new = j_prev + 1
新的疲劳度：如果今天的净消耗net > 0，则f_new = f_prev + 1，否则f_new = f_prev。同时必须满足f_new <= M。
DP值更新：dp[i][j_new][f_new] = max(dp[i][j_new][f_new], dp[i-1][j_prev][f_prev] + net)

情况二：第i天选择休息前提条件：无（任何时候都可以选择休息）。状态转移：

新的连续运动天数：j_new = 0（休息打断了连续）
新的疲劳度：f_new = 0（休息日疲劳度清零）
DP值更新：dp[i][0][0] = max(dp[i][0][0], dp[i-1][j_prev][f_prev])。注意，休息日当天的净消耗为0，所以只累加之前的DP值。

最终答案：遍历第N天（即i = N）的所有可能状态dp[N][j][f]（其中j和f为任意合法值），取其中的最大值，即为所求的最大总净消耗。

实操心得：在推导状态转移方程时，我习惯在纸上画一个简单的状态机图。把(j, f)作为一个节点，用箭头表示“运动”或“休息”决策带来的状态跳转。这样能非常直观地检查转移逻辑是否完备，有没有漏掉某些状态（比如从高疲劳度休息后，是否所有j和f都能回到(0,0)）。对于复杂DP，这个习惯能帮你节省大量调试时间。

3. 多语言实现详解：同样的算法，不同的工程表达

理解了核心算法，我们来看看如何在Python、Java、C++中实现它。这里不仅能看出语言语法差异，更能体现不同语言在工程实践上的特点。我会给出完整的、可运行的代码，并附上关键注释。

3.1 Python实现：简洁与高效的平衡

Python以其极致的简洁性著称，非常适合在机试中快速实现算法原型。我们用列表推导式和清晰的逻辑来构建三维DP数组。

def max_weight_loss(N, K, M, exercise, food): """ 计算小明减肥的最大净消耗。 :param N: 总天数 :param K: 最大连续运动天数 :param M: 最大疲劳度 :param exercise: 列表，长度为N，每天运动消耗 :param food: 列表，长度为N，每天食物摄入 :return: 最大净消耗值 """ # 初始化一个非常小的负数，表示不可达状态 INF_NEG = -10**9 # dp[i][j][f] # 第一维大小 N+1（0到N天），第二维大小 K+1（0到K天），第三维大小 M+1（0到M疲劳度） dp = [[[INF_NEG] * (M + 1) for _ in range(K + 1)] for _ in range(N + 1)] dp[0][0][0] = 0 # 起始状态 for i in range(1, N + 1): # 遍历每一天 net = exercise[i-1] - food[i-1] # 第i天的净消耗，注意索引偏移 for j_prev in range(K + 1): # 遍历前一天所有可能的连续运动天数 for f_prev in range(M + 1): # 遍历前一天所有可能的疲劳度 if dp[i-1][j_prev][f_prev] == INF_NEG: continue # 如果前一天状态不可达，跳过 # 决策1：今天运动 (前提：j_prev < K) if j_prev < K: j_new = j_prev + 1 # 计算新疲劳度：如果净消耗为正，疲劳度+1 f_new = f_prev + (1 if net > 0 else 0) if f_new <= M: # 疲劳度不能超限 new_val = dp[i-1][j_prev][f_prev] + net if new_val > dp[i][j_new][f_new]: dp[i][j_new][f_new] = new_val # 决策2：今天休息 j_new_rest = 0 f_new_rest = 0 new_val_rest = dp[i-1][j_prev][f_prev] # 休息日当天净消耗为0，不增加 if new_val_rest > dp[i][j_new_rest][f_new_rest]: dp[i][j_new_rest][f_new_rest] = new_val_rest # 遍历最后一天的所有状态，找出最大值 ans = INF_NEG for j in range(K + 1): for f in range(M + 1): ans = max(ans, dp[N][j][f]) return ans # 测试用例 if __name__ == "__main__": N, K, M = 5, 2, 1 exercise = [300, 200, 400, 100, 500] food = [200, 300, 100, 400, 200] result = max_weight_loss(N, K, M, exercise, food) print(f"最大净消耗为: {result}") # 根据我们的状态设计，需要运行程序得出结果

Python实现要点与避坑指南：

列表初始化：[[[INF_NEG] * (M + 1) for _ in range(K + 1)] for _ in range(N + 1)]这个嵌套列表推导式是创建三维数组的常用写法。注意不要用[[[INF_NEG] * (M+1)] * (K+1)] * (N+1)，这会导致内部列表是同一个对象的引用，修改一个值会影响到其他位置，这是Python新手常踩的坑。
索引处理：题目和代码中的天数索引通常从1开始，但Python列表索引从0开始。所以exercise[i-1]对应第i天的数据。这个细节在调试时至关重要。
负无穷初始化：我们用-10**9代表负无穷（-inf），这是一个经验值，只要它比任何可能出现的合法结果都小即可。在Python中，也可以使用float(‘-inf’)，但在一些判等比较中需要小心。
性能考虑：三层循环（天数、j、f）的时间复杂度是O(N * K * M)。在本题约束下（假设N, K, M都在100左右）完全可行。但如果维度很大，需要考虑优化，例如滚动数组压缩掉“天数”这一维，将空间复杂度从O(NKM)降到O(K*M)。

3.2 Java实现：严谨与面向对象

Java代码更显严谨，类型明确，结构清晰。我们使用三维数组，并注意循环边界和条件判断。

public class WeightLossPlan { public static int maxWeightLoss(int N, int K, int M, int[] exercise, int[] food) { final int INF_NEG = -1_000_000_000; // 用一个足够小的数表示负无穷 // dp[i][j][f] int[][][] dp = new int[N + 1][K + 1][M + 1]; // 初始化所有状态为负无穷 for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) { for (int f = 0; f <= M; f++) { dp[i][j][f] = INF_NEG; } } } dp[0][0][0] = 0; // 起始状态 for (int i = 1; i <= N; i++) { int net = exercise[i - 1] - food[i - 1]; // 第i天的净消耗 for (int jPrev = 0; jPrev <= K; jPrev++) { for (int fPrev = 0; fPrev <= M; fPrev++) { int prevVal = dp[i - 1][jPrev][fPrev]; if (prevVal == INF_NEG) { continue; // 不可达状态，跳过 } // 决策1：今天运动 if (jPrev < K) { int jNew = jPrev + 1; int fNew = fPrev + (net > 0 ? 1 : 0); if (fNew <= M) { int newVal = prevVal + net; if (newVal > dp[i][jNew][fNew]) { dp[i][jNew][fNew] = newVal; } } } // 决策2：今天休息 int newValRest = prevVal; // 休息日无当日净消耗 if (newValRest > dp[i][0][0]) { dp[i][0][0] = newValRest; } } } } // 找出最后一天所有状态中的最大值 int ans = INF_NEG; for (int j = 0; j <= K; j++) { for (int f = 0; f <= M; f++) { ans = Math.max(ans, dp[N][j][f]); } } return ans; } public static void main(String[] args) { int N = 5, K = 2, M = 1; int[] exercise = {300, 200, 400, 100, 500}; int[] food = {200, 300, 100, 400, 200}; int result = maxWeightLoss(N, K, M, exercise, food); System.out.println("最大净消耗为: " + result); } }

Java实现要点与避坑指南：

数组初始化：Java中int数组默认初始化为0。我们必须显式地遍历整个三维数组，将其初始化为INF_NEG，否则状态0（净消耗为0）和不可达状态就无法区分。
常量定义：使用final int INF_NEG定义负无穷常量，使代码更清晰。注意数值范围，-1_000_000_000是Java 7引入的下划线数字字面量，便于阅读。
三元运算符：fPrev + (net > 0 ? 1 : 0)是Java中简洁的条件表达式，等价于if-else。
方法静态性：为了方便在main方法中直接调用，解题方法通常设为static。在实际工程中，可能需要根据情况设计成实例方法。
空间与性能：和Python一样，这里存在O(NKM)的空间开销。在机试环境中，要留意题目给出的数据范围。如果N很大（比如10^5），而K和M很小（比如10），这个三维数组可能内存超限（O(10^5 * 10 * 10) = 10^7量级，尚可接受但需警惕）。这时就必须使用滚动数组优化，只保留dp[i-1]和dp[i]两层。

3.3 C++实现：性能与控制力的体现

C++版本在语法上更接近Java，但更注重底层控制和性能。我们可以使用vector容器，也可以使用原生数组。这里使用vector更安全方便。

#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; int maxWeightLoss(int N, int K, int M, vector<int>& exercise, vector<int>& food) { const int INF_NEG = INT_MIN / 2; // 使用INT_MIN的一半，避免加法溢出后变成正数 // 初始化三维dp数组，维度为 (N+1) x (K+1) x (M+1)，所有值初始为INF_NEG vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(K + 1, vector<int>(M + 1, INF_NEG))); dp[0][0][0] = 0; for (int i = 1; i <= N; ++i) { int net = exercise[i - 1] - food[i - 1]; for (int j_prev = 0; j_prev <= K; ++j_prev) { for (int f_prev = 0; f_prev <= M; ++f_prev) { int prev_val = dp[i - 1][j_prev][f_prev]; if (prev_val == INF_NEG) continue; // 决策1: 运动 if (j_prev < K) { int j_new = j_prev + 1; int f_new = f_prev + (net > 0 ? 1 : 0); if (f_new <= M) { int new_val = prev_val + net; if (new_val > dp[i][j_new][f_new]) { dp[i][j_new][f_new] = new_val; } } } // 决策2: 休息 int new_val_rest = prev_val; // 休息日无净消耗增加 if (new_val_rest > dp[i][0][0]) { dp[i][0][0] = new_val_rest; } } } } // 遍历最后一天的所有状态找最大值 int ans = INF_NEG; for (int j = 0; j <= K; ++j) { for (int f = 0; f <= M; ++f) { ans = max(ans, dp[N][j][f]); } } return ans; } int main() { int N = 5, K = 2, M = 1; vector<int> exercise = {300, 200, 400, 100, 500}; vector<int> food = {200, 300, 100, 400, 200}; int result = maxWeightLoss(N, K, M, exercise, food); cout << "最大净消耗为: " << result << endl; return 0; }

C++实现要点与避坑指南：

负无穷的选择：使用INT_MIN / 2而不是INT_MIN。这是因为INT_MIN是-2147483648，如果它加上一个正数net，会发生整数下溢（在C++中是有符号整数的未定义行为，通常会变成一个很大的正数），导致比较出错。用INT_MIN / 2留出了足够的“安全边际”。
vector初始化：vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(K + 1, vector<int>(M + 1, INF_NEG)));这个初始化语句虽然长，但清晰地构造了一个三维向量，并且所有元素初始化为INF_NEG。这是C++中创建多维动态数组的推荐方式，比手动new/delete更安全。
循环变量：使用前缀自增++i，这是一种习惯，对于内置类型它与i++性能无差异，但对于迭代器等复杂类型可能更优。
输入输出：使用cin/cout，在机试中通常够用。如果数据量极大，可以考虑使用scanf/printf或关闭cin/cout同步流来加速。
空间优化提醒：同样地，如果N很大，这个三维vector会消耗大量内存（大约(N+1)*(K+1)*(M+1)*4字节）。机试平台通常有内存限制（如256MB或512MB），必须评估。例如，若N=1000, K=10, M=10，内存约为10011111*4 ≈ 484KB，很小；但若N=100000，就变成约48MB，仍在可接受范围，但若K和M也很大就需要警惕了。

实操心得：多语言实现的共通思维无论用哪种语言，DP的核心骨架是完全一致的：定义状态、初始化边界、推导转移、获取答案。在机试中，我建议先用你最熟悉的语言（很可能是Python）快速把算法逻辑写出来并验证。因为Python代码短，调试快。一旦逻辑正确，再翻译成Java或C++就是体力活了，主要注意语法差异和边界条件。千万不要在紧张的考试中，用不熟悉的语言去挑战一个复杂的算法，那会大大增加出错概率。

4. 算法优化与边界情况处理

一个完整的解决方案，不仅要能解决标准用例，还要考虑性能优化和边界情况，这体现了工程师的思维深度。

4.1 空间优化：滚动数组技巧

我们注意到，在状态转移方程中，dp[i][...][...]只依赖于dp[i-1][...][...]。也就是说，我们不需要保存全部N天的状态，只需要保存“前一天”和“今天”两天的状态即可。这可以大幅降低空间复杂度。

我们定义两个二维数组dp_prev[j][f]和dp_curr[j][f]，分别代表前一天和今天的状态。每过一天，就将dp_curr赋值给dp_prev，然后清空dp_curr进行新一轮计算。

以下是Python的滚动数组优化版本：

def max_weight_loss_optimized(N, K, M, exercise, food): INF_NEG = -10**9 # 只保留两个二维数组：前一天和今天 dp_prev = [[INF_NEG] * (M + 1) for _ in range(K + 1)] dp_curr = [[INF_NEG] * (M + 1) for _ in range(K + 1)] dp_prev[0][0] = 0 # 第0天状态 for i in range(1, N + 1): net = exercise[i-1] - food[i-1] # 清空今天的状态数组，重新初始化为负无穷 dp_curr = [[INF_NEG] * (M + 1) for _ in range(K + 1)] for j_prev in range(K + 1): for f_prev in range(M + 1): if dp_prev[j_prev][f_prev] == INF_NEG: continue val_prev = dp_prev[j_prev][f_prev] # 决策：运动 if j_prev < K: j_new = j_prev + 1 f_new = f_prev + (1 if net > 0 else 0) if f_new <= M: new_val = val_prev + net if new_val > dp_curr[j_new][f_new]: dp_curr[j_new][f_new] = new_val # 决策：休息 new_val_rest = val_prev if new_val_rest > dp_curr[0][0]: dp_curr[0][0] = new_val_rest # 今天变成昨天，为下一天迭代做准备 dp_prev, dp_curr = dp_curr, dp_prev # 交换引用，高效且避免深拷贝 # 最后，dp_prev 存储的是第N天的状态 ans = INF_NEG for j in range(K + 1): for f in range(M + 1): ans = max(ans, dp_prev[j][f]) return ans

优化效果：空间复杂度从 O(N * K * M) 降至 O(K * M)。这是一个巨大的提升，尤其当N很大时。在机试中，如果遇到MLE（内存超限）的错误，滚动数组往往是DP问题的第一优化选择。

4.2 边界情况与测试用例设计

一个健壮的程序必须能处理各种边界输入。我们在编写和测试时，要主动考虑这些情况：

最小输入测试：N=1, K=1, M=0。测试程序在最小规模下的正确性。
全休息情况：如果所有exercise[i]都远小于food[i]，导致每天净消耗都为负，最优策略可能是全程休息（净消耗为0）。我们的算法是否能正确处理？答案是肯定的，因为休息决策始终存在，且DP数组初始值为负无穷，最终答案至少为0（从起始状态一直休息下来）。
极限约束测试：K=0（不允许连续运动，即每天最多运动一天？不，K=0意味着不能连续运动，但题目逻辑中j_prev < K的条件永远不成立，所以实际上一天都不能运动）。或者M=0（不能有任何疲劳，即只要某天运动且净消耗为正，就违规）。我们的算法应该能正确处理，最终答案可能是0（全程休息）或一个有限值（如果某天净消耗非正，运动不产生疲劳，则可能运动）。
大数测试：输入数据可能很大，净消耗累加值可能超出int范围。在Java和C++中，dp数组和结果应使用long（Java）或long long（C++）类型。Python的int是任意精度，通常无需担心。
无效输入处理：虽然机试通常保证输入有效，但养成检查习惯是好的。例如，检查exercise和food数组长度是否等于N，K和M是否为非负整数等。

我们可以编写一个简单的测试函数来验证：

def test_cases(): # 用例1：题目假设示例 N, K, M = 5, 2, 1 ex = [300, 200, 400, 100, 500] fd = [200, 300, 100, 400, 200] print(f"Test 1: {max_weight_loss_optimized(N, K, M, ex, fd)}") # 用例2：全休息最优 N, K, M = 3, 2, 10 ex = [10, 10, 10] # 消耗小 fd = [100, 100, 100] # 摄入大，净消耗为负 # 运动只会让总净消耗减少，所以最优策略是休息，答案为0 print(f"Test 2 (全休息): {max_weight_loss_optimized(N, K, M, ex, fd)}") # 用例3：必须运动，但受疲劳度限制 N, K, M = 3, 3, 1 ex = [500, 10, 500] fd = [100, 100, 100] # 净消耗都为正值。如果三天都运动，疲劳度会变成3，超过M=1。 # 最优策略可能是：运动、休息、运动。总净消耗 = (500-100)+0+(500-100)=800 print(f"Test 3 (疲劳限制): {max_weight_loss_optimized(N, K, M, ex, fd)}") # 用例4：单天测试 N, K, M = 1, 1, 0 ex = [400] fd = [200] # 净消耗为正，但M=0，运动会产生疲劳度1，超过M，所以不能运动？不，疲劳度是在运动且净消耗为正时才+1。 # 这里净消耗200>0，运动后疲劳度f_new = 0 + 1 = 1，超过了M=0，所以运动决策无效。 # 只能休息，答案为0。 print(f"Test 4 (单天M=0): {max_weight_loss_optimized(N, K, M, ex, fd)}") if __name__ == "__main__": test_cases()

通过设计这些测试用例，我们不仅能验证代码正确性，还能加深对状态转移逻辑的理解，尤其是约束条件是如何起作用的。

5. 华为OD机试实战技巧与备考策略

最后，结合这道“小明减肥”真题，我分享一些华为OD机试的实战技巧和备考建议，这些是我和身边朋友多次实战后的经验总结。

5.1 机试中的时间分配与答题策略

华为OD机试通常是3道题，150分钟。时间非常紧张。合理的策略是：

第一题（简单）：通常是字符串处理、简单数学或模拟题。目标15分钟内解决，确保100%通过。这道题是保底分，必须拿下。
第二题（中等）：通常是数据结构应用，如二叉树、链表、哈希表，或中等难度的DP、BFS/DFS。目标40-50分钟。这类题就像“小明减肥”，有明确的算法套路，但需要仔细实现。
第三题（困难）：通常是复杂DP、图论（最短路径、最小生成树）或高级数据结构（并查集、线段树）。目标60分钟以上。如果前两题已稳，可以全力攻坚；如果没把握，则应确保拿到部分分（比如通过简单的测试用例）。

对于“小明减肥”这类中等题，我建议的答题流程是：

5分钟读题与抽象：彻底理解题意，识别出DP模型（最优子结构、重叠子问题）。在草稿纸上写出关键变量和约束。
10分钟设计状态与方程：这是最关键的一步。定义出dp[i][j][f]这样的状态，并推导出转移方程。务必考虑全面（运动、休息两种决策，以及各种前提条件）。
20分钟编码与调试：用你最熟悉的语言，将上述思路转化为代码。先写核心DP循环，再补全输入输出。在本地用样例测试。
5分钟检查与优化：检查边界条件（数组索引、初始值）。思考是否有优化空间（如滚动数组）。提交前，在脑中再过一遍极端情况。

5.2 常见错误排查清单

在实现DP时，尤其是机试紧张环境下，以下错误非常常见：

数组索引越界：dp数组大小是[N+1][K+1][M+1]，循环时for i in range(1, N+1)，但取exercise[i-1]。务必保持一致。
状态初始化错误：忘记将不可达状态初始化为负无穷，或者错误地将dp[0][0][0]初始化为0以外的值。
状态转移条件遗漏：比如在“运动”决策中，忘记了检查j_prev < K和f_new <= M这两个前提条件。
疲劳度计算逻辑错误：错误地将“疲劳度+1”的条件设定为“只要运动就+1”，而题目可能是“运动且净消耗为正才+1”。必须严格按题意编码。
答案提取错误：最后不是取max(dp[N][j][f])，而是错误地取了dp[N][K][M]。最终状态可以是任意合法的(j, f)组合。

调试技巧：对于DP问题，最好的调试方法是打印出小规模测试用例的整个dp表（或关键部分），手动模拟一遍，看状态转移是否符合预期。例如，对于N=2, K=1, M=1的简单情况，把dp[0], dp[1], dp[2]都打印出来核对。

5.3 备考资源与练习建议

题库选择：优先练习华为OD历年真题。真题最能反映出题风格和难度。像“小明减肥”这类生活化场景的DP题，在真题库中很常见（如“分月饼”、“快递投放”、“任务调度”等）。
算法重点：华为OD对动态规划、深度/广度优先搜索、二叉树、链表、双指针、滑动窗口、排序的考察频率极高。必须熟练掌握这些算法的模板和变种。
语言准备：选择一门你最熟练的语言作为主力。Python在编码速度上有巨大优势，适合快速实现算法。Java和C++在性能要求极高的场景下有优势，但更考验代码功底。不要临阵换语言。
模拟练习：在牛客网、LeetCode等平台的ACM模式下练习。华为OD机试是ACM模式，需要自己处理输入输出。务必熟悉如sys.stdin.read()（Python）、Scanner（Java）、cin（C++）的用法。
错题总结：建立一个错题本。不仅记录错题，更要记录当时为什么错（是题意理解偏差？状态设计错误？还是边界条件遗漏？）。定期回顾，避免重复犯错。