LeetCode-1326. Minimum Number of Taps to Open to Water a Garden

LeetCode-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: 1Explanation: 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: -1Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]Output: 3

Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]Output: 2

Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]Output: 1

Constraints:

​​1 <= n <= 10^4​​​​ranges.length == n + 1​​​​0 <= ranges[i] <= 100​​

题解：

之前按点算的，一直不对，看讨论区是按区间算的，dp[1]代表0-1这个区间。

动态规划问题：先遍历每个喷头的喷射范围，然后计算范围内需要的喷头最小数。

class Solution {public: int minTaps(int n, vector& ranges) { vector dp(n + 1, 1000); dp[0] = 0; for (int i = 0; i <= n; 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], dp[left] + 1); } } if (dp[n] >= 1000) { return -1; } return dp[n]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。