給出一堆range值，ranges[i]表示第i個(gè)tap可以覆蓋[i-ranges[i], i+ranges[i]]，問最少幾個(gè)tap可以覆蓋[0, n]，如果不存在輸出-1，O(n*m)dp
1 #1326
2 #Runtime: 467 ms (Beats 26.32%)
3 #Memory: 13.6 MB (Beats 94.74%)
4
5 class Solution(object):
6 def minTaps(self, n, ranges):
7 """
8 :type n: int
9 :type ranges: List[int]
10 :rtype: int
11 """
12 dp = [0] + [n + 2] * n
13 for i, x in enumerate(ranges):
14 for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
15 dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
16 return dp[n] if dp[n] < n + 2 else -1