Задача: 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].

😎 Решение:

var minTaps = function(n, ranges) {
    const INF = Number.MAX_SAFE_INTEGER;
    const dp = new Array(n + 1).fill(INF);
    dp[0] = 0;
    
    for (let i = 0; i <= n; i++) {
        const tapStart = Math.max(0, i - ranges[i]);
        const tapEnd = Math.min(n, i + ranges[i]);
        
        for (let j = tapStart; j <= tapEnd; j++) {
            dp[tapEnd] = Math.min(dp[tapEnd], dp[j] + 1);
        }
    }
    
    return dp[n] === INF ? -1 : dp[n];
};

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