class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<int> state(n+1, INT_MAX);
        for (int i = 0; i < state.size(); i++)
        {
            int l = i - ranges[i];
            int r = min(n, i + ranges[i]);
            if (l <= 0)
            {
                for (int j = 0; j <= r; j++)
                    state[j] = 1;
            }
            else
            {
                for (int j = l; j <= r; j++)
                {
                    if (state[l] != INT_MAX)
                        state[j] = min(state[j], state[l]+1);
                }
            }
        }
        return state[n] == INT_MAX ? -1 : state[n];
    }
};