Задача: 1326. Minimum Number of Taps to Open to Water a Garden
Сложность: 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 {
    public int minTaps(int n, int[] ranges) {
        int INF = (int) 1e9;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        
        for (int i = 0; i <= n; i++) {
            int tapStart = Math.max(0, i - ranges[i]);
            int tapEnd = Math.min(n, i + ranges[i]);
            
            for (int j = tapStart; j <= tapEnd; j++) {
                dp[tapEnd] = Math.min(dp[tapEnd], dp[j] + 1);
            }
        }
        
        return dp[n] == INF ? -1 : dp[n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний