1326. 灌溉花园的最少水龙头数目 动态规划

1326. 灌溉花园的最少水龙头数目

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

示例 1：

输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示：

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

 

做题结果

失败，完全没思路，因为一般这种题都是枚举的，这100不能用位运算，就很迷茫

方法：动态规划

1. 确定左右边界，在右边界的位置标记左边界，选择尽量靠左的边界

2. 链接上一段，在本段范围内，选择上一段的基础上+1

3. 注意不存在的右端点直接跳过

class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] prev = new int[n+2];
        Arrays.fill(prev,n);
        for(int i = 0; i < ranges.length; i++){
            int left = Math.max(0,i-ranges[i]);
            int right = Math.min(n,i+ranges[i]);
            prev[right]=Math.min(left,prev[right]);
        }
        // System.out.println(Arrays.toString(prev));
        int []dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE/2);
        dp[0]=0;
        for(int i = 1; i <= n; i++){
            if(prev[i]==n) continue;
            for(int j = prev[i];j<i;j++){
                dp[i] = Math.min(dp[i],dp[j]+1);
            }
        }
        return dp[n]<Integer.MAX_VALUE/2?dp[n]:-1;
    }
}