华为od笔试题python

华为OD笔试题是关于使用动态规划解决工作报酬问题的。给定工作总时长t，工作数量n，工作时间数组time和工作报酬数组earnings，需要选择一些工作使得总时长不超过t，并且获得最大的报酬。

有两种解法可以解决这个问题。解法1是使用二维dp数组，解法2是使用一维dp数组进行优化。

解法1中，我们创建一个二维dp数组，dp\[i\]\[j\]表示在前i个工作中，总时长不超过j的情况下能获得的最大报酬。然后使用两层循环遍历工作和时长，根据状态转移方程dp\[i\]\[j\] = max(dp\[i-1\]\[j\], dp\[i-1\]\[j-time\[i-1\]\] + earnings\[i-1\])来更新dp数组。最后返回dp\[-1\]\[-1\]即为最大报酬。

解法2是对解法1的优化，使用一维dp数组。我们只需要保存上一行的dp值，然后从后向前遍历时长，根据状态转移方程dp\[j\] = max(dp\[j\], dp\[j-time\[i-1\]\] + earnings\[i-1\])来更新dp数组。最后返回dp\[-1\]即为最大报酬。

以上是关于华为OD笔试题的解答。
#### 引用[.reference_title]
- *1* *3* [华为OD笔试题：工作安排 --- 100分 （思路+python代码）](https://blog.csdn.net/m0_69258561/article/details/130973186)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [【100%通过率】华为OD机试真题 Python 实现【分奖金】【2022.11 Q4 新题】](https://blog.csdn.net/misayaaaaa/article/details/128420154)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]