1326. Minimum Number of Taps to Open to Water a Garden

leetcode hard

#array#csharp#dynamic-programming#hard#intervals#leetcode#math

Task

Есть одномерный сад на оси 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]

C# solution

matched/original

public class Solution {
    public int MinTaps(int n, int[] ranges) {
        const int INF = int.MaxValue;
        int[] dp = new int[n + 1];
        Array.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];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinTaps(int n, vector<int>& ranges) {
        const int INF = int.MaxValue;
        vector<int>& dp = new int[n + 1];
        Array.Fill(dp, INF);
        dp[0] = 0;
        
        for (int i = 0; i <= n; i++) {
            int tapStart = max(0, i - ranges[i]);
            int tapEnd = min(n, i + ranges[i]);
            
            for (int j = tapStart; j <= tapEnd; j++) {
                dp[tapEnd] = min(dp[tapEnd], dp[j] + 1);
            }
        }
        
        return dp[n] == INF ? -1 : dp[n];
    }
}

Java solution

matched/original

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];
    }
}

JavaScript solution

matched/original

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];
};

Explanation

Algorithm

Объявите массив dp размера n+1. Инициализируйте его значениями бесконечности (в коде используем большое число 10^9 для представления бесконечности). Установите dp[0] в 0 (базовый случай DP).

Итерируйтесь от i до n (через каждый кран слева направо). Рассчитайте самую левую позицию, достижимую текущим краном, как tap_start=max(0,i−ranges[i]). И самую правую позицию tap_end=min(n,i+ranges[i]).

Итерируйтесь через позиции j от tap_start до tap_end (в пределах досягаемости крана). Обновите dp[tap_end] значением dp[j]+1, если оно меньше. Если dp[n] остается бесконечным, значит, полить весь сад невозможно, и мы возвращаем −1. Верните dp[n].

😎