GFG 洒水器的最少数量

洒水器的最少数量

有一个长度为 N 的一维花园。

已安装。给定一个数组 a[]，其中 a[i] 描述了第 i 个洒水器的覆盖范围。

的覆盖范围。洒水器的覆盖范围为 max（i - a[i]，1）到 min（i + a[i]，N）。

开始时，所有自动喷水灭火装置都处于关闭状态。

我们的任务是找出需要启动的最小洒水器数量，从而使整个 N 长的花园都能被水覆盖。

注：数组以 1 为索引。

示例 1：

输入：a[] = {1, 2, 1}

输出： 1 1

说明： 对于位置 1：a[1] = 1，范围 = 1 至 2：

位置 1：a[1] = 1，范围 = 1 至 2

位置 2：a[2] = 2，范围 = 1 至 3

位置 3：a[3] = 1，范围 = 2 至 3

因此，位置 a[2] 的喷泉覆盖整个花园。因此，所需的输出为 1。

例 2：

输入：a[] = {2, 1, 1, 2, 1} 

输出 2 

解释：位置 1：a[1] = 2，范围 = 1 至 3：

位置 1：a[1] = 2，范围 = 1 至 3

位置 2：a[2] = 1，范围 = 1 至 3

位置 3： a[3] = 1，范围 = 2 至 4

位置 3： a[4] = 2，范围 = 2 至 5

位置 3：a[5] = 1，范围 = 4 至 5

因此，位置 a[1] 和 a[4] 的喷泉覆盖了整个花园。因此 

答案也可能是 a[2] 和 a[4]。

通过DeepL.com（免费版）翻译

---------

dp，我用的数组，结果老是错，有时候还不知道错误在哪里。