1326.minimum-number-of-taps-to-open-to-water-a-garden.java

/*
 * @lc app=leetcode id=1326 lang=java
 *
 * [1326] Minimum Number of Taps to Open to Water a Garden
 *
 * https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/description/
 *
 * algorithms
 * Hard (40.82%)
 * Likes:    127
 * Dislikes: 36
 * Total Accepted:    5.8K
 * Total Submissions: 14.2K
 * Testcase Example:  '5\n[3,4,1,1,0,0]'
 *
 * 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.
 * 
 * 
 * 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
 * 
 */

// @lc code=start
class Solution {
	public int[] dp;
	public int callme(int cur, int n, int[] ranges){
		if(cur >= n)	return 0;
		if(dp[cur] != 0)	return dp[cur];

		int ret = Integer.MAX_VALUE;
		for(int i=cur; i<=Integer.min(cur+100, n) ; i++)
			if(i-ranges[i] <= cur && ranges[i] != 0)
				ret = Integer.min(ret, callme(i+ranges[i], n, ranges));
		if(ret == Integer.MAX_VALUE)
			return dp[cur] = ret;
		return dp[cur] = ret+1;
	}

    public int minTaps(int n, int[] ranges) {
        dp = new int[n+1];
        int ret = callme(0, n, ranges);
        if(ret == Integer.MAX_VALUE)	return -1;
        return ret;
    }
}
// @lc code=end