x軸上的花園范圍為[0,n], 0~n這個(gè)n+1個(gè)離散點(diǎn)上有水龍頭，第 i 個(gè)水龍頭能澆水的范圍為[i-ranges[i], i+ranges[i]].
求能澆整個(gè)花園的最小水龍頭個(gè)數(shù)。

思路：

方法一：
greedy

先把每個(gè)水龍頭能澆的區(qū)間準(zhǔn)備好，
用一個(gè)數(shù)組保存所有區(qū)間，數(shù)組下標(biāo)為區(qū)間起點(diǎn)，數(shù)組內(nèi)容為區(qū)間終點(diǎn)。

然后從左到右遍歷這個(gè)數(shù)組，到這里就和55題Jump Game類似了。
用一個(gè)變量canReach表示到目前的水龍頭為止能澆到的最遠(yuǎn)距離。preEnd表示前一個(gè)水龍頭的區(qū)間終點(diǎn)。

如果當(dāng)前位置 > preEnd，說明需要開一個(gè)新的水龍頭，
但是如果這時(shí)canReach <= preEnd（前一水龍頭處能澆到的最遠(yuǎn)距離也無法到達(dá)當(dāng)前位置，后面有說明），說明無法到達(dá)，返回-1.
更新preEnd到canReach (canReach這時(shí)還沒有更新，即preEnd更新到前一個(gè)水龍頭為止的最遠(yuǎn)范圍). 水龍頭個(gè)數(shù)+1.
把canReach更新到和當(dāng)前區(qū)間終點(diǎn)相比的較大值。

有一個(gè)特殊情況要注意下，就是Example2中ranges[i]=0的情況。
注意能澆水到整個(gè)花園說明不止是離散點(diǎn)i , i+1, …能澆到，i 到 i+1之間的連續(xù)點(diǎn)部分也必須在區(qū)間中。
而ranges[i] = 0 表示只能澆到離散點(diǎn) i 本身。比如1，2點(diǎn)能澆到，但它們之間的1.1, 1.2, …都不在澆灌范圍。
所以在處理區(qū)間時(shí)，canReach必須能到達(dá)當(dāng)前點(diǎn)才算滿足條件。

    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是前一區(qū)間滿足條件時(shí)在當(dāng)前區(qū)間加的，最后一個(gè)區(qū)間沒有下一區(qū)間去處理，所以要在最后處理一下//如果preEnd能到達(dá)最后位置，就不需要cnt+1,如果到不了，需要再cnt++,preEnd更新到canReachreturn cnt + (preEnd < n ? 1 : 0);}

方法二：

DP
dp[i ] 表示澆到 i 位置所需的水龍頭個(gè)數(shù)。
開始的時(shí)候，除了dp[0]，其他全部初始化為無窮大。

還是像上面一樣從左到右計(jì)算每個(gè)水龍頭的澆水區(qū)間。
區(qū)間內(nèi)每個(gè)點(diǎn)處所需的最少水龍頭個(gè)數(shù)dp[ i ] = min(dp[i], dp[區(qū)間的起點(diǎn)]+1).
這是什么意義呢？
因?yàn)閐p[0]=0, 當(dāng)更新水龍頭0的區(qū)間時(shí)，都會(huì)以dp[0]+1為準(zhǔn)，把0處的水龍頭能澆到的范圍內(nèi)，每個(gè)點(diǎn)處所需水龍頭個(gè)數(shù)更新為1.
假設(shè)第一個(gè)區(qū)間為[0,2]，更新如下
1 1 1 Inf Inf Inf
這時(shí)假如進(jìn)入下一區(qū)間[2,4]，那么在2的位置，仍然可以保持dp[2]=min(dp[2], dp[2]+1)=1.
到了位置3時(shí)，dp[3]=min(Inf,dp[2]+1)就變成需要2個(gè)水龍頭。
同樣的，如果前一范圍覆蓋不到后面的區(qū)間，就會(huì)出現(xiàn)min(inf, inf+1)的情況。
最后返回dp[n], 如果dp[n]為Inf, 說明無法澆到整個(gè)花園，返回-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];}