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

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, …, n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<int> dp(n + 1, n + 2);
        dp[0] = 0;
        for(int i = 0; i <= n; i++) {
            for(int j = max(0, i - ranges[i] + 1); j <= min(n, i + ranges[i]); j++) {
                dp[j] = min(dp[j], dp[max(0, i-ranges[i])] + 1);
            }
        }
        return dp.back() == n + 2 ? -1 : dp.back();
    }
};