[Question]
  [
You work at a beach. In the afternoon, the sun gets quite hot and beachgoers want to be shaded. So you put out umbrellas. When you put out umbrellas you want to shade the entire beach, with as few umbrellas as possible.
Umbrellas come in many sizes. However, larger umbrellas are susceptible to being pulled away by the wind, so in the morning you have to go to the beach and do a soil test. The soil test tells you, for each spot on the beach, the size of the largest umbrella that could be safely placed.
So after your soil test, you get back a list of positive integers. For example:
```
[2,1,3,1,3,1,1,2,1]
```
Each number represents the maximum radius of an umbrella that can be placed at that location. A radius \$r\$ umbrella covers itself, and \$r-1\$ spots to both its left and right.
For example a radius 3 umbrella covers:
* itself
* the two spaces directly adjacent to it,
* the two further spaces adjacent to those,
Your task is to write a computer program which takes the results of the soil test as a list of positive integers, and gives back the minimum number of umbrellas required to cover all the spots on the beach.
For example if the soil test gives back `[2,1,4,1,4,1,1,3,1]`, then you can cover the beach with 2 umbrellas:
```
            X X X X X
X X X X X X X   |
      |         |
 [_,_,4,_,_,_,_,3,_]
```
So the output of the program should be 2.
This is code-golf so the goal is to minimize the size of your source code as measured in bytes.
## Test cases
```
[9,2,1,3,2,4,2,1] -> 1
[9,9,9,9,9,9,9,9] -> 1
[1,1,1,1,1,1,1,1] -> 8
[2,1,4,1,4,1,1,3,1] -> 2
[5,1,3,1,3,1,1,1,6] -> 2
[4,1,1,3,1,1] -> 2
```
  
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~30~~ ~~27~~ 26 bytes
```
Ôº∑‚Äπ‚Ü®œÖ‚Å∞Ôº¨Œ∏‚äûœÖ‚åàÔº•Œ∏‚àß‚Äπ‚ÅªŒª‚Ü®œÖ‚Å∞Œ∫‚Å∫ŒªŒ∫Ôº©Ôº¨œÖ
```
[Try it online!](https://tio.run/##RY0xC8IwEIV3f8WNFzjBopuTujaQvXQ4ajChaWybRP33MaGCd7w3fMd7Nxhehye7nN/GOg3Y6hDwykFjIjgIglb7RzS4CCFApWAql/yxU5pQ8owLwcXft5y0PgV0BP@C0jAWKbcdRlHnvFOr9RFvHCL@HqTKc@66hk7UlD1W7/u8f7kv "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Explanation: Greedy algorithm.
```
Ôº∑‚Äπ‚Ü®œÖ‚Å∞Ôº¨Œ∏
```
Until all of the beach has been covered, ...
```
‚äûœÖ‚åàÔº•Œ∏‚àß‚Äπ‚ÅªŒª‚Ü®œÖ‚Å∞Œ∫‚Å∫ŒªŒ∫
```
... filtering on those umbrellas whose left end is not to the right of the first uncovered index, pick the one that maximises the next uncovered index.
```
Ôº©Ôº¨œÖ
```
Output the number of umbrellas used.
Edit: Saved 1 byte by porting @tsh's optimisation. Example: Take the input `[1,4,1,1,3,1,1]`. Initially, five umbrellas lie to the right of index `0`, the valid two being the `1` at index `0` itself, and the `4` at index `1`, which also covers indices `1` to `4`. The maximum next uncovered index is therefore `5`, obtained by choosing the `4`. The `1` at index `6` is the only umbrella to the right of index `5`, and the maximum next uncovered index is therefore `7`, obtained by choosing the `3`. This completes the coverage of the beach using two umbrellas.
A port of @Jonas' J solution was also 27 bytes:
```
ÔºµÔº≠Œ∏Ôº•Œ∏¬¨‚Äπ‚Üî‚ÅªŒºŒ∫ŒπÔº∑‚åà‚åäŒ∏¬´‚Üí‚âß√ó‚åäŒ∏Œ∏¬ªÔº©‚äï‚Öà
```
[Attempt this Online!](https://ato.pxeger.com/run?1=PU6xCsIwEJ3brwhOV0iHooPoJJ0EKyIOQukQa7TBJrG9VAXxS1wcFB31c_wb0yrewT3u3rt7d36kGStTzfLL5VaZld99PyO2DbWUTC2hoMR2NYy1gRFHhMECdV4ZDpFQFYKkZON5lAjPRt_dZyLnBCJ2ELKStabBwpLk6DqR3nHoTcU6M1bs2NsDRLFWzQRmQnK0jv8lSgorO7mTUigDIUMDQ5WWXHJl-BLm0JhecZHi7_t73PJ3eSt5xXFAOzSw2a5rknz5Dw "Charcoal ‚Äì Attempt This Online") Link is to verbose version of code. Explanation:
```
ÔºµÔº≠Œ∏Ôº•Œ∏¬¨‚Äπ‚Üî‚ÅªŒºŒ∫Œπ
```
Convert each umbrella into a list of `0`s and `1`s where the `0`s are the locations that are covered.
```
Ôº∑‚åà‚åäŒ∏¬´
```
Repeat until opening an umbrella will cover the beach.
```
‚Üí
```
Keep count of the number of umbrellas opened.
```
‚âß√ó‚åäŒ∏Œ∏
```
Zero out the locations covered by the largest remaining umbrella.
```
¬ªÔº©‚äï‚Öà
```
Output the number of umbrellas required.
Previous 30-byte brute force solution:
```
Ôº©‚åäÔº•Œ¶Ôº∏¬≤Ôº¨Œ∏‚¨§Œ∏‚äôŒ∏‚Äπ‚Üî‚ÅªŒºŒæ√óŒΩÔπ™√∑ŒπÔº∏¬≤Œæ¬≤Œ£‚çòŒπ¬≤
```
[Try it online!](https://tio.run/##PY7NCoMwEIRfJccVtgdtbz3ZlkJBQbA38ZBqsAv5qSax7dOnRqQDO3PYj2G6J586w2UI1UTawZlbByVpUl5ByV9wJenEBJV5L54hK4Qe3BPGJEGWSwnjEvoboxDWQv6wRnonYoe3oJB9InknJSxoZKXpvTRw0@5CM/UCCNm/e0WzZBWyellw4lbUblk2RHB7HUNomgxTPGyX4h7Ttg27Wf4A "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Explanation:
```
     ¬≤                          Literal integer `2`
    Ôº∏                           Raised to power
       Œ∏                        Input array
      Ôº¨                         Length
   Œ¶                            Filter over implicit range
         Œ∏                      Input array
        ‚¨§                       All indices satisfy
           Œ∏                    Input array
          ‚äô                     Any value satisfies
               Œº                Inner index
                Œæ               Innermost index
              ‚Åª                 Difference
             ‚Üî                  Absolute value
            ‚Äπ                   Is less than
                     Œπ          Outer value
                    √∑           Integer divided by
                       ¬≤        Literal integer `2`
                      Ôº∏         Raised to power
                        Œæ       Innermost index
                   Ôπ™            Modulo
                         ¬≤      Literal integer `2`
                 √ó              Multiplied by
                  ŒΩ             Innermost value
  Ôº•                             Map over implicit range
                            Œπ   Current value
                           ‚çò    Convert to base
                             ¬≤  Literal integer `2`
                          Œ£     Take the sum (i.e. popcount)
 ‚åä                              Take the minimum
Ôº©                               Cast to string
                                Implicitly print
```
[Answer]
## C89, 89 bytes
**-11 bytes thanks to @Martin Kealey**
```
int m,i,x;f(v,n)int*v;{for(i=n;i--;m=abs(m-i)<x?x+i:m)x=v[i];return m>=n?m=0,1:1+f(v,n);}
```
[Try it online!](https://tio.run/##dZLRToMwFIbveYoTvKGunbDpsq3rFm9MjCY@AFkMsjFPMoqBQoikry62dLpo9DSnPeV8@Qt/SVl6TOShv0CZHuvdHlaV2mExfl33KBXkFGnLs6Chkpj9ZcO7rCgDFJIjYzwXyUsV5AzJqt20I1zmpBVNjFte7lVdSsjXQm5yEdJoGY2cDNdOOUEZNAXuSOeBiUqVdao62yo52KWJp5OtKyXXoOItCHCwjS6i0C3ohEZ0auZrW2nqenNNz9ycWvbH@JObUJuRUXJpdU/k4jd347pD2jH7h/vWOZ9pY6YHTHPPfTu@758VIB92xmAwDtuHRQbq6quIQ@sGY@uQkwE8e/FWqyrIAmWcHzcUhlUSEMKVJWzAf3rwYQn@3e39o0/cSe4thul0XyH3tNd/pNkxOVQ9M/@CSOeLTw "C (clang) ‚Äì Try It Online")
```
int m, i, x;
int f(int *v, int n)
{
    for(i=n; i--;)
    {
        extern int abs();
        x = v[i];
        if (abs(m-i) < x) m = x+i;
    }
    
    if (m>=n){
        m = 0;
        return 1;
    }
    else { 
        return 1 + f(v, n);
    }
}
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~16~~ 13 bytes
-3 thanks to @KevinCruijssen
```
gDŒ¥Œ±‚Ä∫√¶ í√∏O√ü}√∏g
```
[Try it online!](https://tio.run/##yy9OTMpM/f8/3eXclnMbHzXsOrzs1KTDO/wPz689vCP9//9oIx1DHRMoNtQx1jGMBQA "05AB1E ‚Äì Try It Online")
## Explanation
```
g         # push the length
D         # twice
Œ¥Œ±        # create the 2D array a[i][j] = abs(i-j)
‚Ä∫         # compare each value to the correct value in the input
√¶         # take the powerset
 í         # and keep sets such that:
 √∏         # if transposed
 O         # and summed
 √ü         # the minimum value
}         # (is 1)
√∏         # transpose
g         # and return the length
```
Requiring that the minimum is 1 is valid because in an optimal solution exactly one umbrella covers the leftmost position.
Transposing and then taking the length finds the minimum length, due to the way transposing works on different-sized arrays.
`Œ¥‚Ä∫√Ö\` really feels like it can be shorter, but I can't find anything.
[Answer]
# [R](https://www.r-project.org), 61 bytes
```
f=\(b,p=l,l=sum(b|1))sum(if(p>0)1+f(b,min((1:l-b)[1:l+b>p])))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72waMGq0tykotScnMRi26WlJWm6Fjdt02xjNJJ0CmxzdHJsi0tzNZJqDDU1QYzMNI0COwNNQ-00oHxuZp6GhqFVjm6SZjSQ0k6yK4jV1NSEGvIYbqxGsoaljpGOoY4xkDQBsTQ1FZQVdO0UDLmQFRnqoECYIgsURSBzTKAYZCJcmRGKMlOIJBiDoBl2ZSApI6gSY1RrTRRQVJog1CCMgnh1wQIIDQA)
**Ungolfed code**
```
f=function(b,p=1){ # begin at position p=1
    l=length(b)
    s=1:l-b+1 # start positions of umbrellas
    e=1:l+b-1 # end positions of umbrellas
    if(p>l)0  
    else 1+f(b,max(e[s<=p])+1) 
              # update position to 
              # furthest end of umbrella  
              # with start before current position
}
```
[Answer]
# [J](https://www.jsoftware.com), 36 34 33 31  33 bytes
```
{{1>.#}.(OR>./)^:a:#.y>|@-/~#\y}}
```
[Attempt This Online!](https://ato.pxeger.com/run?1=dZDBSsNAEIbxmqeYZLWb2M0ku2ppFhqWCp6kQvHWptCWBCuCYNJDie2LeIkHH6o-jZuskfQgw7Aw3_ezs_vx-VwdLyJb8mRgy4hSy0GawUgCBQYhSN0-wu30_u5rW2T-8GiXJY-R7NF9mMYYeAu5lAR38bvygwOZ7_Z7I36fTTxrMkbgRGm5j855WCZzucFe6PAmplyTUhtUpJUxLN1A8h5BT7mCyBouiOfOyGEmLwOH9zHQdtKJWpaVrp9eATIQjLPr3-bsinFD6GOaF7Be5mlOzYTDSOsRE40mdEC08rBBnJ2UQaJB_1xi4I0ZNV3XoAv_EjpTP3e8Xa1e0jeaQ9EueLJet8y3VpU5fwA)
*-1 thanks to Bubbler suggesting a conversion to explicit fn.*
*Also thanks to Bubbler for pointing out a bug when a single umbrella covers everything, which must be handled as a special case.*
Inspired by [Neil's idea](https://codegolf.stackexchange.com/a/266062/15469), but with an array implementation.
Consider the example `2 1 4 1 4 1 1 3 1`:
* `y>|@-/~#\y` For each entry in the list, this shows what the beach would look like with only that umbrella open, using a `1 0` list. The full phrase returns a binary matrix, with each row showing one "isolated umbrella" version of the beach:
```
1 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 0
0 0 0 1 0 0 0 0 0
0 1 1 1 1 1 1 1 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1
```
* `#.` Interpret those as binary numbers:
```
384 128 504 32 254 8 4 15 1
```
Conceptually, we'll still be working with `1 0` lists, but using integers will help us shorten the necessary computations.
* `(...^:a:)` Accumulate the results of `...` until a fixed point...
* `(...>./)` On each iteration, we find the row with the farthest rightward span of ones, provided that span starts at the left:
```
1 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 0  <- farthest rightward span
0 0 0 1 0 0 0 0 0
0 1 1 1 1 1 1 1 0  <- doesn't count since it starts with 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1
```
This row, however, is nothing but the largest integer in our list, because of how binary numbers work.
* `(OR...)` We then add that "farthest right" row elementwise to every row, essentially "blocking out" everything it covers from all rows. This is nothing but the bitwise `OR` operation. The transformation in this step corresponds to our chosen umbrella being deployed:
```
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1
```
Then we continue. Our process will reach a fixed point (a matix of all ones) in `n + 1` steps, where `n` is the minimum number of covering umbrellas.
* `#}.` So we kill one element and get the length.
* `1>.` Finally, we return the max of that length and 1. This is needed for the case where a single umbrella covers the entire beach, because otherwise the algorithm above will return 0 in this case.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 60 bytes
```
a=>(g=i=>a[i]&&-~g(a.reduce((m,r,j)=>j-i<r&r+j>m?r+j:m)))(0)
```
[Try it online!](https://tio.run/##dY1RC4IwFIXf@xV7kl2a2kyjoq0fIj4MnbKhLmb12F9fTkVI6B7O4cL9OFeLtxhKqx7PsDeVdDVzgnHcMMW4yFURBOGnwSKysnqVEuOOWKKBcR2qmw3sXvPuPua1AwB8AFeafjCtjFrT4BrnF5IQSo5jpn4rEAJAcYzobgNS8qMVPG9B35cu9s20mMFkC2bzebLX6R@4Nk1v/Syg@wI "JavaScript (Node.js) ‚Äì Try It Online")
---
# [Python 3](https://docs.python.org/3/), 73 bytes
```
f=lambda a,i=0:i<len(a)and-~f(a,max(r+j for j,r in enumerate(a)if j-i<r))
```
[Try it online!](https://tio.run/##ZY3RCsIwDEXf/YqALy1mYLcpU7YvkT1E1mLL1o0yQV/89bp2uiHmckMIJzfDc7z1NvNeVS1114aAUFf7sy5baRlxsk3yUoywowdzOwOqd2DQgbYg7b2TjkY5cVqBSXTpOPeD03Zkil1OmKLAbOp5mGoAzmELYrMQAn/0JYqVCAn5xyFL1JFIV@Iw76ODjn/Echs/hJoJ/wY "Python 3 ‚Äì Try It Online")
[Answer]
# [Nekomata](https://github.com/AlephAlpha/Nekomata), 13 bytes
```
J·µê{x:·µí‚âà>~}a≈ü#
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m70iLzU7PzexJHFZtJJurlLsgqWlJWm6Flu8Hm6dUF1h9XDrpEedHXZ1tYlH5ysvKU5KLoYqWHAzMtpSx0jHUMcYSJqAWLFc0YY6KBAoAlJhAsUgtSAxUwgLjEHQDCgGlweqgNgAAA)
```
J·µê{x:·µí‚âà>~}a≈ü#
J               Split the list into parts
 ·µê{x:·µí‚âà>~}      Check that each part can be covered by an umbrella:
 ·µê{      }          For each part:
   x:·µí‚âà                 Create a table a[i][j] = abs(i-j)
       >~               Check that there is at least one row in the table
                        that is smaller than the corresponding item in the input
          a≈ü    Find the shortest solution
            #   Take the length
```
This may output the same result multiple times. For example, the input `[2,1,4,1,4,1,1,3,1]` can be split into `[[2,1,4,1,4],[1,1,3,1]]` or `[[2,1,4,1,4,1],[1,3,1]]`, and the output is `2` in both cases.
[Answer]
# JavaScript (ES6), 87 bytes
Brute force.
```
a=>(g=(i,b=a,v=a[i++])=>v?Math.min(g(i,b),1+g(i,b.map(q=>--i*i<v*v?0:q))):b.join``*i)``
```
[Try it online!](https://tio.run/##dY3hCoIwFIX/9xT7uemczSxKmj5BTyCC09QmumnKXt@aipDQPdzLgfNxbs01H/K36EZHqmcxlWziLIQVgwJnjGPNeCxsO0Es1NGDjy/SCgkrkyJM7dmQlnewZ6HjCEvctaWjY9AjhIKM1ErINLUEStMpV3JQTUEaVcESxjfsYYpP3@sblwCAEHBdQA87kOIfbeB1D5o@f13TTJMF9PbgeYnnNbr8A7em@a2ZFZw@ "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# [Python](https://www.python.org), 182 bytes
*-2 bytes, thanks to xigoi*
```
lambda l:(S:={*range(L:=len(l))})and[len(c)for n in S|{L}for c in combinations([range(i-k+1,i+k)for i,k in enumerate(l)],n)if{L}.union(*({*r}for r in c))>S][0]
from itertools import*
```
[Attempt This Online!](https://ato.pxeger.com/run?1=bY6xTsMwEED3foUlFjt1KlIKaiOlX9AtY8jgpjZYsc-R6wyo9EtYIiEYGfkX_gY7qZIiodP5fPK753v7bF7cs4HuXWSPH60T8frnWzG9PzCkUpyn2SmyDJ443qWZ4oAVIWfC4FCEpiLCWARIAspfT7tz6KrQVUbvJTAnDRxxMQhkXM8TKud1PyRpHUAOreaWOe7FJQUihdcsWvCDOML-795peych27wsbsuZsEYj6bh1xqgjkrox1kWX7b8aK8FhgYsNXdKE3vlzFW4lIegGxVuUzEYkoX9iRNYTEhyrSwbbBC0n6H546jPEw3_QaLh2DFt33VB_AQ)
## ungolfed code:
```
import itertools
def f(l):
 l=[range(i-k+1,i+k)for i,k in enumerate(l)]
 S={*range(L:=len(l))}
 for n in range(len(l)+1):
  for c in itertools.combinations(l,n):
   s=set()
   for r in c:
    s|={*r}
   if s>S: # s=S not possible as L in s\S
    return len(c)
```
Brute force solution, goes through all possible sets of umbrellas ordered by size and picks the first one that covers the whole range
[Answer]
# JavaScript, 62 bytes
```
f=(a,s=0)=>a[s]?1+f(a,Math.max(...a.map((v,i)=>i-v<s&&i+v))):0
```
[Try it online!](https://tio.run/##VYrRCsIgGIWv6ym8Gsr@yVYrKFo9QU8gXohpWdscU6Se3rS6icM5fHycuwjCydlMvnKTuah5sONDvWLUHRbgupp0R8EcPzWlTuIs/I0O4okppSLBhHEAkz6mCgdXFKYMhJB9HbWdEe6VR14iqxFjO1hBA@u0bSYOrIG/JJMf7a/5m93mS5/mbDkny4W0o7O9or29Yo29JCS@AQ "JavaScript (SpiderMonkey) ‚Äì Try It Online")
Greedy algorithm: pick the umbrella that covers the most spaces while including the first uncovered space.
[Answer]
# [sed](https://www.gnu.org/software/sed/), 424 bytes
Thank you for restricting umbrella sizes to 9, otherwise `sed` stops to be the natural choice for solving this thing. (-; The maximum number of umbrellas is also limited to nine; you can upgrade to the big-beach-edition for a couple of extra bytes as an in-app-purchase.
I got distracted so often, that I decided to publish this initial version solving the problem, although I'm feeling that there are still ten to twenty bytes to golf away on a rainy day.
How it works:
* loop `1` creates all possible combinations of umbrellas used or not
* loop `2` sorts those combinations by their number of umbrellas used, which is awfully slow with this approach for 2^beachsize combinations!
* loop `3` takes one combination after the other to test whether they cover the beach with those sub-elements:
	+ loop `4` makes a separate line for each umbrella
	+ loop `5` opens the umbrellas by couting down there size and spreading `=`
	+ loop `6` transposes the beaches from lines to columns (this will probably only work with wet sand)
	+ if there is a line without umbrella, this means sun will hit the beach, so we have to start with the next combination of loop `3`
* loop `7` finally counts the number of umbrellas in the first shady combination
```
G
s/^/_/
:1
s/(\S*)_(\S)(\S*.)/\1-_\3\1\2_\3/
t1
:2
s/-(\S*_)/0\1#/
s/(\S*_(#*)\n)(\S*_\2#+\n)/\3\1/
t2
h
:3
s/\S*\n//
x
s/_.*/\n/
:4
s/^(-*)([0-9])(\S*.)/\1-\3\1\2_\3/
s/_\S/-_/
t4
s/-*/987654321#/
:5
s/((.)(.).*#.*)\2/\1x\3x/
s/(x=*)-/\1=/
s/-(=*)x/=\1/
s/x//g
t5
s/#./&!_/
s/\n//g
:6
s/!(.*_)([^x])/!\2\1x/
t6
s/_x*/_/g
s/!/!\n/
/__/!t6
s/!/!#/
/\n[-0]+(\n|_)/!b7
g
b3
:7
s/((.)(.).*!)\3(.*)1.*/\1\2\4/
t7
s/.*!(.).*/\1/
```
[Try it online!](https://tio.run/##TZDBasMwDIbvfosQGLaLrdpOm9XQ49gD9Fi1hrKR7ZIOkoEPe/Zlv8IOheDI@n9Jnzy9v7lh/F6WVzXRlQqpHBBpPllTcBqJvCEOrnDiwBE/UnNQOcLnRC6Gthxa@q8rurWGx7WycGw3iElqURbVh8oJRmg8EqmKuHhLuKjcCYN21ujz1h0uD7MfRsPPJ3IgncXvLB2e@/2uS1EQ8k4otDf4vG09SCIaVE515atHaxwSR1rpcat0FLSJKtGgZqlvPT01RXLCOKi8R9hoj031@VovhhqOaAoEUUq1eLhBPBCwCJVCzSohASi0ObvtZaN5/MFjNbdeDeqWVO4fYRvDCTNMkOfAttyhvzggrQYSzmXpQkghxPB7/5o/7@O0uJc/ "sed ‚Äì Try It Online")
*Note that beaches of 8 parts or bigger will time out on TIO. Adding a `g` flag in the sorting part of the second loop drastically reduces execution time, but still not enough for hard cases.*
[Answer]
# Python3, 358 bytes
```
E=enumerate
F=lambda h,i,a:{*[i+j for j in range(1,a)if i+j<len(h)]+[i-j for j in range(1,a)if i-j>=0],i}
def f(h):
 q,m=[(F(h,i,a),1)for i,a in sorted(E(h),key=lambda x:x[1])[::-1]],-1
 while q:
  a,b=q.pop(0)
  if len(a)==len(h):m=b if m==-1 else min(m,b);continue
  for x,y in E(h):
   if x not in a and(m==-1or b+1<m):q=[({*a,*F(h,x,y)},b+1)]+q
 return m
```
Non-greedy (where is the fun otherwise?) with a basic heuristic for the sake of speed.
[Try it online!](https://tio.run/##dVDBTsMwDL33K3xMNhctDBCEhdv2E1UPKU1pRpO2WSc6Tfv24nSAtAOKHDl@79nP6U5D3fr1cxemaauMPzoT9GCSnWq0K0oNNVrU8rzI7HIPVRtgD9ZD0P7DMIGa2woI2TTGs5rny8ym/9LS/Zta5WgvSWkqqIgvE@jRqYzt2DyHo@BRTGmUH9owmJJtiYmf5vRraZRjJnKeSZmKPMdUJPBV28ZAT/1AY6H6u67t2IrTkwZHb5ordfUonSpi1SmVCjDNwYCznjks@Ot76wfrj4Z00caIp2hje3U69xrBt0MsatC@ZHMTYhZLsXFc9rTKeaFxEfchNb8gIfQtfQLBDMfgwU1dsH5gFcte8B4Frul@iFnOefKHCbw5N1hUPfxE1N@ij9faHPE8ETp9Aw)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~18~~ 17 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
x<Ls-ƒÅ¬©+√¶ íÀú¬Æ√•P}√∏g
```
-1 byte thanks to *@CommandMaster*.
[Try it online](https://tio.run/##yy9OTMpM/f@/wsanWPdI46GV2oeXnZp0es6hdYeXBtQe3pH@/3@0kY6hjgkUG@oY6xjGAgA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeX/ChufYt0jjYdWah9edmrS6TmH1h1eGlB7eEf6f53/0dGWOkY6hjrGQNIExIrViTbUQYFAEZAKEygGqQWJmUJYYAyCZrGxAA).
**Explanation:**
```
x<      # Calculate the width of each umbrella:
x       #  Double each value in the (implicit) input-list (without popping)
 <      #  Decrease each by 1
Ls-ƒÅ¬©+  # Convert each to 1-based ranges it can cover:
L       #  Convert each inner value to a [1,value]-ranged list
 s-     #  Subtract the values of the input-list from each value of the lists
   ƒÅ +  #  Add the 1-based indices
    ¬©   #  And also store the list of 1-based indices in variable `¬Æ`
√¶ íÀú¬Æ√•P} # Get all combinations of umbrellas that cover the entire beach:
√¶       #  Get the powerset of this list of lists
  í    } #  Filter it by:
  Àú     #   Flatten the list of lists
   ¬Æ√•P  #   Check whether it contains all 1-based indices of value `¬Æ`
√∏g      # Output the least amount of umbrellas necessary to cover the beach:
√∏       #  Zip/transpose; swapping rows/columns,
        #  discarding any trailing items of unequal length lists
 g      #  Pop and push the length
        # (which is output implicitly as result)
```
[Try it step-by-step.](https://tio.run/##VY6hTgNBEIY9TzE52624FkUgFRU1TVrfIGa3Q2@TvV2yMwtFIHgFNBYSDJKgryh4qOO216ZBjJr/@/4/MGpLbVtM0ZnkUAikIri3a6kg3AChqSDVOpJzeAGF2l5eNZ@Ts2Ia/B1F6QMSoBxqZFpDRL8hBitg0IMJXShjcx5@PzXvgx6ekQA6171rbT2KDZ5z27GIuxEoPb3fQ15sJNC5Let2bz/Pvy/Nx@51@dgrF0luk@zDjpA7fx2Sl/9WT4aYMT7kxSf7Sfu1mbTtaqRKdX64Uo1Vef0H)
[Answer]
# [JavaScript (SpiderMonkey)](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Releases/45), 76 bytes
```
f=(a,k=0,b=-1)=>a[k]?1+Math.min(...a.map((v,i)=>i>b&v+k>i?f(a,v+i,i):1/0)):0
```
[Try it online!](https://tio.run/##dY1RCoMwDIbfd4o@jRZrtc6NTVBPsBOID9Xp1lWtqBR2@q5VESYs4Q8h@fLnzRQby4H3kzv2/FENrexE9dG6jiHDIvZxEbsUxQnLRJ5S586mF2l5BwkhjLSsh1BhbvY8KY7KEQlPa3OoHG6mEfV8hCJfl7IbZVORRj5hDbMbDjDFJ1ND2@UAIAQ8D9DDDqT4JzfwugetX7jKOtN8AYM9eF7Ws2xe/oGb0/zWxgrqLw "JavaScript (SpiderMonkey) ‚Äì Try It Online")
Try to fix m90's error
[Answer]
# APL (Dyalog Unicode), 78 bytes
```
‚åä/b/‚ç®√ób‚Üê{(+/‚çµ)√ó‚àß/(1@(‚àä{n(1‚åà‚åä)(‚ç≥¬Ø1+2√ó‚çµ‚å∑v)+‚çµ-‚çµ‚å∑v}¬®‚çµ/‚ç≥n))n‚ç¥0}¬®{‚çµ‚ä§‚ç®n‚ç¥2}¬®‚ç≥¬Ø1+2*n‚Üê‚ç¥v
```
Another brute force attack. The index origin is set to 1 (‚éïIO‚Üê1). The variable v contains the integer vector to be evaluated.
I have some more work to do on this one. It is a bit convoluted as it is. I think I'm missing something obvious.
[Try it on TryAPL.org!](https://tryapl.org/?clear&q=%E2%8C%8A%2Fb%2F%E2%8D%A8%C3%97b%E2%86%90%7B(%2B%2F%E2%8D%B5)%C3%97%E2%88%A7%2F(1%40(%E2%88%8A%7Bn(1%E2%8C%88%E2%8C%8A)(%E2%8D%B3%C2%AF1%2B2%C3%97%E2%8D%B5%E2%8C%B7v)%2B%E2%8D%B5-%E2%8D%B5%E2%8C%B7v%7D%C2%A8%E2%8D%B5%2F%E2%8D%B3n))n%E2%8D%B40%7D%C2%A8%7B%E2%8D%B5%E2%8A%A4%E2%8D%A8n%E2%8D%B42%7D%C2%A8%E2%8D%B3%C2%AF1%2B2*n%E2%86%90%E2%8D%B4v%E2%86%902%201%204%201%204%201%201%203%201%0A2&run)
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~102 100~~ 97 bytes
```
->l{(r=*1..l.size).find{|c|r.combination(c).any?{|x|r&x.flat_map{|a|[*a-l[-a]+1...a+l[-a]]}==r}}}
```
[Try it online!](https://tio.run/##VU7RisIwEHzvV@RJtLYrrVXuwOqL9@oPrOFYYwOBNC3RO/SafnttcxWUYZdhhhnG/pzuncy7eKubqc3DBEDDRf0VM5DKnBsnnAVRlSdl6KoqMxUzIHPfNe7m7OQGUtP1u6S6ceQwpFhjTHzetwDNPedtntu2bbuaScQsSnosh895ULPN5uuwB61McQHfIpzE4pc0E7g4IoRHvugrAvyMUh9Mo2xgnMVblgzyG55yEr3Byx8BDhXZeH6FN9IAV@Oo5ZhYP43Xvf9Sv7d7AA "Ruby ‚Äì Try It Online")
Thanks value ink for some good ideas (-2/-3 bytes)
[Answer]
# [Desmos](https://desmos.com/calculator), ~~169~~ 168 bytes
```
L=l.count
I=[1...L]
B=mod(floor(2n/2^I),2)
k=i-l[i]
H=[1...k]0
A=[min(‚àë_{i=1}^Ljoin(H[k>H],[1...2l[i]-1+min(k,0)]0+1,I0)[I]B[i])B.totalforn=[1...2^L]]
f(l)=A[A>0].min
```
[Try It On Desmos!](https://www.desmos.com/calculator/jwxvjlvn20?nographpaper)
[Try It On Desmos! - Prettified](https://www.desmos.com/calculator/hmmay3qe6m?nographpaper)
This brute forces every single umbrella combination, so expectedly this is very slow. In fact, this took about 40 or so seconds to finish running on my computer LOL.
Also, the code is absolutely horrendous and can definitely be golfed. I mean, just look at it....
[Answer]
**Raku 68 bytes**
```
map({$^a-$^b+1..^$^a+$^b},@_.kv).combinations.grep(^@_‚äÜ*)>>.elems.min
```
simple brute force approch
[Try it online!](https://tio.run/##K0gtyjH7n1up4JCoYKugYaRjqGMCxYY6xjqGmtZc/6tzEws0qlXiEnVV4pK0DfX0gExtIFPXsFbHIV4vu0xTLzk/NykzL7EkMz@vWC@9KLVAI84h/lFXm5amnZ1eak5qbrFebmZerYZDoqZecWLl//8A "Perl 6 ‚Äì Try It Online")
[Answer]
# [Scala](http://www.scala-lang.org/), 113 bytes
Port of [@tsh's Python code](https://codegolf.stackexchange.com/a/266097/110802) in Scala.
---
Golfed version. [Try it online!](https://tio.run/##fY1BawIxEIXv/oo5zmBcN9aWdukWPArtSXoSD6lNtgkxanYOFvG3bxOrBWEpw8ybeXy8adfKq2774fSa4U3ZAMfuUxswqKqF3i/ngVfCVknqks5iDdpnVXgdGv4iOUykwBJ4C1dzJKkw1rOO6OoXN0o4OqJio3bZyMfQ5fNA2rcaym4AkJ9u0n9UsWkrmMWovpcLjjY0K6rgPViGGo6JBNgll31Ag6@2ZXwSEyHFXZrTvBERjMcg@1ApbuqCPvahOXN66Zx@hSd98P0vcu5cD//Bf4k3mafBqfsB)
```
def f(a:Seq[Int],i:Int=0):Int=if(i<a.length)1+f(a,(0 to a.length-1).filter(j=>j-i<a(j)).map(j=>a(j)+j).max)else 0
```
Ungolfed version. [Try it online!](https://tio.run/##fZBRS8MwFIXf@yvOY4Jxa@cULU7wUdEn8WnsIc6kpqSxpJlMpL@9Jmu6WShyueHm3o@Te9JsueZd9/lWiq3DM1cGPwnwLiQk4TmeVOPWD8ZtGFQOX2CFlA5VQAElQRRuwWdamMJ90NgHvrhGxfePu6r2NEmxM07pExgxYCaVdsKSEqs7lDjHQY@U9A9S8bqfhz7OUI5m@3jJ/MRvzoZ3e6iF0I047pX2zSRkdFt564Tboslxby3/Xr84q0yx8V5fjTqZrX3XaUMkCV9DbtiCZezCn8tQUUoxnyObQjM2ioheT6FBcxkzqA/wYgq@7JFDhrj6Dz4qjjTbpO26Xw)
```
object Main {
  def f(a: List[Int], i: Int = 0): Int = {
    if (i < a.length) {
      val maxJump = (0 until a.length)
        .filter(j => j - i < a(j))
        .map(j => a(j) + j)
        .max
      1 + f(a, maxJump)
    } else {
      0
    }
  }
  def main(args: Array[String]): Unit = {
    println(f(List(9,2,1,3,2,4,2,1))) // 1
    println(f(List(1,1,1,1,1,1,1,1))) // 8
    println(f(List(2,1,4,1,4,1,1,3,1))) // 2
    println(f(List(5,1,3,1,3,1,1,1,6))) // 2
    println(f(List(4,1,1,3,1,1))) // 2
  }
}
```
[Answer]
# [Python](https://www.python.org), 200 bytes
Not a very competitive answer, but it's the best I can do with the baseline python functions.
* l: is list of the beach spaces
* r: radius of already covered spaces
* p: amount of umbrellas and the final answer
Function goes through the beach from the left, finds the right most umbrella placing which covers all uncovered space to its left and reaches the farthest right.
The function then starts again with the spaces to the right of the last placed umbrella and now with info of which spaces on the left are already covered. When all spaces are covered prints out number of placed umbrellas.
Any tips for making this more streamlined are welcome, thank you.
```
def f(l,r=0,p=0):
    m=r
    for u in range(len(l)):
        s=l[u]-1
        if u-s-r<1 and u+s>=m:
            m=u+s
            t=u
    if m>len(l)-2: return p+1
    else: return f(l[t+1:],m, p+1)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=VZDBbsMgDIbvPIWPRDFSabtpi0ZfJMqhVWGLRGhE4LDX2HWXXrZn2Sv0bYoDzRRbBuvTb2P8_Tt-ho-Lu15_YjDi5fZ31gYMt-jVBke1qRoGyQbl59tcPEToHfije9fcasdtVTRkk7Jt7IRcQG8gikn4NwlHd4ZYTwc1_Otz70RXJKjISvFwyG-IbQNeh-gdjHVur-2kF5hGbkMtmw4HJEVV_vNlFbTtK25R4i6de8o6ZAmtnJDElROisn0JajDDp5zOQf5McFEkTccYLepEi7L5s6PvXeCGn6oy2WPjdw)
]