1. 动态规划与双指针在华为 OD 机试中的重要性
华为 OD 机试向来以算法题为核心考察点，其中动态规划和双指针算法出现的频率尤其高。就拿最近几场机试来说，'找车位'和'高效的任务规划'这两道动态规划题几乎成了必考题，而双指针也经常以各种变体形式出现。
为什么华为这么偏爱这两种算法？从实际开发场景来看，动态规划特别适合解决资源优化类问题，比如任务调度、路径规划等华为业务中的常见需求。而双指针在数据处理、字符串操作等基础场景中效率极高。例如经典的'滑动窗口求最大平均数'，本质上就是双指针的变种。
2. 动态规划实战：停车位问题详解
2.1 问题描述与建模
'找车位'问题的典型描述是：给定一个只包含 0 和 1 的数组，1 表示已有车辆停放，0 表示空位。要求找到一个停车位，使得该位置到最近车辆的距离最大。比如数组 [1,0,0,0,1,0,1]，最优解是下标 2 的位置，此时最近距离为 2。
这个问题可以分解为两个子问题：
- 从左向右遍历，记录每个位置左侧最近的 1 的距离
- 从右向左遍历，记录每个位置右侧最近的 1 的距离
最终结果是这两个距离中的较小值，再取所有位置中的最大值。这种'分解子问题 + 组合结果'的思路就是动态规划的典型特征。
2.2 代码实现与优化
def max_parking_distance(spaces):
n = len(spaces)
left = [float('inf')] * n
right = [float('inf')] * n
# 从左向右扫描
last = -float('inf')
for i in range(n):
if spaces[i] == 1:
last = i
left[i] = i - last
# 从右向左扫描
last = float('inf')
for i in range(n - 1, -1, -1):
if spaces[i] == 1:
last = i
right[i] = last - i
# 计算最大最小距离
max_dist = 0
for i in range(n):
dist = min(left[i], right[i])
dist > max_dist:
max_dist = dist
max_dist
