1. 灌溉花园问题解析：贪心与动态规划的双重视角
遇到这个题目时，我正在力扣上刷动态规划专题。题目描述很简单：花园由n个位置组成，每个位置需要特定水量，洒水器有固定灌溉范围，要求用最少洒水器覆盖整个花园。但当我真正动手实现时，才发现这个看似简单的问题背后藏着算法选择的艺术。
这个问题之所以经典，在于它完美展现了贪心算法和动态规划两种不同思维方式的碰撞。作为算法工程师，我们经常要在二者之间做选择——贪心算法简洁高效但适用面窄，动态规划普适性强但实现复杂。下面我就结合自己AC这道题的全过程，分享两种解法的实现细节和选择逻辑。
2. 问题建模与核心难点
2.1 问题重述与抽象化
给定长度为n的花园，每个位置i需要a[i]单位水量。洒水器安装在若干位置，每个洒水器能覆盖区间[i - range, i + range]，且每次灌溉可提供1单位水。求使整个花园获得足够水量的最少洒水器开启次数。
示例： 输入：a = [1,2,1,2,1], range = 1 输出：3 解释：位置1、3、5各开启一次洒水器
2.2 关键难点分析
这个问题的特殊之处在于：
- 覆盖范围与位置相关（非固定区间）
- 水量需求是累加的（同一区域可能被多个洒水器覆盖）
- 需要同时考虑空间覆盖和水量的双重约束
注意：实际编码时要特别处理边界条件。比如当range=0时，洒水器只能灌溉当前位置，这时问题退化为简单的累加求和。
3. 贪心算法解法详解
3.1 算法选择依据
当发现问题的"贪心选择性质"时，就该考虑贪心算法了。具体到本题：
- 局部最优：每次选择能覆盖当前最左未满足位置的最远洒水器
- 全局最优：这种局部选择能导向全局最优解
3.2 具体实现步骤
def min_sprinklers_greedy(a, range): n = len(a) events = [] for i in range(n): left = max(0, i - range) right = min(n - 1, i + range) events.append((left, right)) res = 0 pos = 0 while pos < n: max_right = -1 # 在能覆盖pos的洒水器中选右边界最大的 for i in range(n): if events[i][0] <= pos <= events[i][1]: max_right = max(max_right, events[i][1]) if max_right == -1: # 无法覆盖 return -1 res += 1 pos = max_right + 1 return res3.3 时间复杂度优化
原始实现是O(n²)，可以通过预处理优化：
- 按左端点排序所有区间
- 使用双指针扫描，优化内层循环
优化后版本：
def min_sprinklers_greedy_opt(a, range): n = len(a) intervals = [] for i in range(n): L = max(0, i - range) R = min(n - 1, i + range) intervals.append((L, R)) intervals.sort() res = 0 i = 0 pos = 0 while pos < n: max_right = -1 while i < n and intervals[i][0] <= pos: max_right = max(max_right, intervals[i][1]) i += 1 if max_right < pos: return -1 res += 1 pos = max_right + 1 return res4. 动态规划解法深度剖析
4.1 为什么需要动态规划？
当贪心策略失效时（比如洒水器有不同成本），就需要更通用的解法。动态规划通过保存子问题解来解决这类问题。
4.2 状态定义与转移方程
定义dp[i]表示覆盖前i个位置所需的最少洒水器数：
dp[i] = min(dp[j] + 1) 对于所有满足 j < i 且 [j+1, i] 能被单个洒水器覆盖的情况初始条件：dp[0] = 0
4.3 完整实现代码
def min_sprinklers_dp(a, range): n = len(a) dp = [float('inf')] * (n + 1) dp[0] = 0 coverage = [[] for _ in range(n)] for i in range(n): L = max(0, i - range) R = min(n - 1, i + range) for j in range(L, R + 1): coverage[j].append(i) for i in range(1, n + 1): for j in coverage[i - 1]: L = max(0, j - range) if dp[L] != float('inf'): dp[i] = min(dp[i], dp[L] + 1) return dp[n] if dp[n] != float('inf') else -14.4 复杂度分析
时间复杂度：O(n²) （预处理O(n²)，DP过程O(n²)） 空间复杂度：O(n)
5. 两种算法的对比与选择
5.1 性能对比
| 指标 | 贪心算法 | 动态规划 |
|---|---|---|
| 时间复杂度 | O(nlogn) | O(n²) |
| 空间复杂度 | O(n) | O(n) |
| 适用场景 | 标准问题 | 变种问题 |
5.2 选择策略
- 优先尝试贪心算法：当问题明显具有贪心选择性质时
- 考虑动态规划：当存在以下情况时：
- 洒水器有不同的开启成本
- 需要记录具体洒水器选择方案
- 问题变形导致贪心策略失效
5.3 常见错误排查
贪心算法常见错误：
- 未处理无法覆盖的情况（返回-1）
- 边界条件处理不当（如range=0）
动态规划常见错误：
- 状态转移条件错误
- 初始条件设置不当
- 数组越界问题
6. 实战优化技巧
6.1 贪心算法的预处理优化
使用跳跃游戏思想，预处理每个位置能到达的最远位置：
def preprocess(a, range): n = len(a) reach = [0] * n for i in range(n): reach[i] = min(i + range, n - 1) return reach6.2 动态规划的状态压缩
当n很大时，可以使用滚动数组优化空间：
# 只保留必要的DP状态 dp_prev = 0 for i in range(1, n + 1): dp_curr = float('inf') # ...计算过程... dp_prev = dp_curr6.3 测试用例设计
好的测试用例应该包含：
- 常规情况
- 边界情况（range=0）
- 无法覆盖的情况
- 大规模数据测试
示例测试集：
test_cases = [ ([1,2,1,2,1], 1, 3), ([0,0,0,0,0], 2, 0), ([1,1,1,1,1], 0, 5), ([1,2,3,2,1], 10, 1), ([1,0,1,0,1], 1, -1) ]7. 问题变种与扩展
7.1 变种1：洒水器有不同成本
此时贪心算法可能失效，必须用动态规划：
- 状态转移方程中cost变为变量
- 需要记录每个位置的最小成本
7.2 变种2：二维花园灌溉
将问题扩展到二维：
- 洒水器覆盖圆形区域
- 使用二维DP或更复杂的贪心策略
7.3 变种3：实时灌溉问题
考虑时间维度：
- 洒水器需要时间启动
- 结合调度算法进行优化
在实际面试中，面试官常常会从基础版本开始，逐步增加约束条件来考察候选人的算法设计能力。我的经验是：先确保基础解法正确，再逐步处理更复杂的变种。
