Сложность: hard
Есть одномерный сад на оси x. Сад начинается в точке 0 и заканчивается в точке n. (т.е. длина сада равна n).
В саду есть n + 1 кранов, расположенных в точках [0, 1, ..., n].
Даны целое число n и целочисленный массив ranges длиной n + 1, где ranges[i] (индексация начинается с 0) означает, что i-й кран может поливать область [i - ranges[i], i + ranges[i]], если он открыт.
Верните минимальное количество кранов, которые должны быть открыты для полива всего сада. Если сад невозможно полить, верните -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]
👨💻 Алгоритм:
1⃣Объявите массив dp размера n+1. Инициализируйте его значениями бесконечности (в коде используем большое число 10^9 для представления бесконечности). Установите dp[0] в 0 (базовый случай DP).
2⃣Итерируйтесь от i до n (через каждый кран слева направо). Рассчитайте самую левую позицию, достижимую текущим краном, как tap_start=max(0,i−ranges[i]). И самую правую позицию tap_end=min(n,i+ranges[i]).
3⃣Итерируйтесь через позиции j от tap_start до tap_end (в пределах досягаемости крана). Обновите dp[tap_end] значением dp[j]+1, если оно меньше. Если dp[n] остается бесконечным, значит, полить весь сад невозможно, и мы возвращаем −1. Верните dp[n].
😎 Решение
class Solution {
func minTaps(_ n: Int, _ ranges: [Int]) -> Int {
let INF = Int.max
var dp = [Int](repeating: INF, count: n + 1)
dp[0] = 0
for i in 0...n {
let tapStart = max(0, i - ranges[i])
let tapEnd = min(n, i + ranges[i])
for j in tapStart...tapEnd {
dp[tapEnd] = min(dp[tapEnd], dp[j] + 1)
}
}
return dp[n] == INF ? -1 : dp[n]
}
}Ставь 👍 и забирай 📚 Базу знаний