无锡网站建设推荐智勇百度友情链接

x轴上的花园范围为[0,n], 0~n这个n+1个离散点上有水龙头，第 i 个水龙头能浇水的范围为[i-ranges[i], i+ranges[i]].
求能浇整个花园的最小水龙头个数。

思路：

方法一：
greedy

先把每个水龙头能浇的区间准备好，
用一个数组保存所有区间，数组下标为区间起点，数组内容为区间终点。

然后从左到右遍历这个数组，到这里就和55题Jump Game类似了。
用一个变量canReach表示到目前的水龙头为止能浇到的最远距离。preEnd表示前一个水龙头的区间终点。

如果当前位置 > preEnd，说明需要开一个新的水龙头，
但是如果这时canReach <= preEnd（前一水龙头处能浇到的最远距离也无法到达当前位置，后面有说明），说明无法到达，返回-1.
更新preEnd到canReach (canReach这时还没有更新，即preEnd更新到前一个水龙头为止的最远范围). 水龙头个数+1.
把canReach更新到和当前区间终点相比的较大值。

有一个特殊情况要注意下，就是Example2中ranges[i]=0的情况。
注意能浇水到整个花园说明不止是离散点i , i+1, …能浇到，i 到 i+1之间的连续点部分也必须在区间中。
而ranges[i] = 0 表示只能浇到离散点 i 本身。比如1，2点能浇到，但它们之间的1.1, 1.2, …都不在浇灌范围。
所以在处理区间时，canReach必须能到达当前点才算满足条件。

    public int minTaps(int n, int[] ranges) {int preEnd = 0;int canReach = 0;int[] startEnd = new int[n+1];int cnt = 0;for(int i = 0; i <= n; i++) {if(ranges[i] == 0) continue;int start = (i - ranges[i] < 0 ? 0 : i - ranges[i]);int end = (i + ranges[i] > n ? n : i + ranges[i]);startEnd[start] = end;}for(int i = 0; i <= n; i++) {if(i > preEnd) {if(canReach <= preEnd) return -1;cnt ++;preEnd = canReach;}if(startEnd[i] > canReach) canReach = startEnd[i];}//cnt是前一区间满足条件时在当前区间加的，最后一个区间没有下一区间去处理，所以要在最后处理一下//如果preEnd能到达最后位置，就不需要cnt+1,如果到不了，需要再cnt++,preEnd更新到canReachreturn cnt + (preEnd < n ? 1 : 0);}

方法二：

DP
dp[i ] 表示浇到 i 位置所需的水龙头个数。
开始的时候，除了dp[0]，其他全部初始化为无穷大。

还是像上面一样从左到右计算每个水龙头的浇水区间。
区间内每个点处所需的最少水龙头个数dp[ i ] = min(dp[i], dp[区间的起点]+1).
这是什么意义呢？
因为dp[0]=0, 当更新水龙头0的区间时，都会以dp[0]+1为准，把0处的水龙头能浇到的范围内，每个点处所需水龙头个数更新为1.
假设第一个区间为[0,2]，更新如下
1 1 1 Inf Inf Inf
这时假如进入下一区间[2,4]，那么在2的位置，仍然可以保持dp[2]=min(dp[2], dp[2]+1)=1.
到了位置3时，dp[3]=min(Inf,dp[2]+1)就变成需要2个水龙头。
同样的，如果前一范围覆盖不到后面的区间，就会出现min(inf, inf+1)的情况。
最后返回dp[n], 如果dp[n]为Inf, 说明无法浇到整个花园，返回-1.

    public int minTaps(int n, int[] ranges) {final int INF = 100000;int[] dp = new int[n+1];Arrays.fill(dp, INF);dp[0] = 0;for(int i = 0; i <= n; i++) {int start = (i-ranges[i] < 0 ? 0 : i-ranges[i]);int end = (i + ranges[i] > n ? n : i+ranges[i]);for(int j = start; j <= end; j++){dp[j] = Math.min(dp[j], dp[start]+1);}}return dp[n] == INF ? -1 : dp[n];}