# 1326. Minimum Number of Taps to Open to Water a Garden

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Constraints:

• 1 <= n <= 104
• ranges.length == n + 1
• 0 <= ranges[i] <= 100

class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> jumps(n + 1);
for (int i = 0; i < n + 1; ++i) {
int left = max(0, i - ranges[i]);
int right = min(n, i + ranges[i]);
jumps[left] = max(jumps[left], right - left);
}
int res = 0, last = 0, farCanReach = 0;
for (int i = 0; i < n; ++i) {
if (i > farCanReach) return -1;
farCanReach = max(farCanReach, i + jumps[i]);
if (i == last) {
++res;
last = farCanReach;
}
}
return farCanReach >= n ? res : -1;
}
};

class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
for (int i = 0; i < n + 1; ++i) {
int left = max(0, i - ranges[i]);
int right = min(n, i + ranges[i]);
for (int j = left; j <= right; ++j) {
dp[j] = min(dp[j], 1 + dp[left]);
}
}
return (dp[n] == n + 1) ? -1 : dp[n];
}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1326

Jump Game II

Video Stitching

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/solutions/486517/c-o-n-no-sort-similar-to-jump-game-ii/

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/solutions/712660/dp-pattern-to-solve-3-similar-problems/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation